解题思路

先把所有能源仓按坐标从小到大排序，记第 $i$ 个能源仓的位置为 $x_i$，可转运的能源为 $c_i$。

由于每个能源仓的收益 $c_i$ 都是正数，所以如果决定经过一段区间 $[L, R]$，那么这段区间内的所有能源仓都应该顺便收集，不会更差。 因此，问题就变成：

• 选择排好序后的一段连续区间 $[l, r]$
• 要求从起点 $s$ 出发，走完这段区间内所有点的最小耗材不超过 $N$

题目内容

戴森环是一种环绕恒星建造、用于收集恒星能量的巨型人造天体结构。多多是负责转运能源的工作人员之一，他负责其中一条贯穿戴森环的直线检修带。本次任务他的飞船将停靠在坐标 $s$ 上，飞船可用于转运任务的总燃料为 $N$ 单位，若消耗超出限制，飞船将无法顺利返航。

多多将沿着这条检修带回收沿途已经集满的能源仓，可以自行规划本次航线，既可以先朝坐标较小的方向推进，也可以先朝坐标较大的方向推进，飞船推进 $1$ 单位距离需要消耗 $1$ 单位燃料，任务途中可任意折返，但折返同样会消耗飞船燃料。能源仓散布在检修带上，不同能源仓由于工艺技术以及设备老化的原因，能够存储的上限能源量并不相同。

第 $i$ 个已集满的能源仓位于坐标 $x_i$ 处，其中储满了 $c_i$ 单位能源，同一个能源仓在本次任务中至多只能完成一次转运，本次收集后则需要重新经历一段时间的积累。请你帮助多多计算本次任务最多能够转运多少单位的能源

输入描述

第一行为一个整数 $T$ ,表示共有 $T$ 个测试数据 $(1<=T<=10)$ 每组测试数据:

第一行两个整数 $N,M,s$,其中 $N$ 为本次转运任务的可用总燃料，$M$ 为本次任务已集满的能源仓总数，$s$ 为本次任务飞船停靠的初始坐标 $(0<=N<= 10^9,1 <= M <= 100000,0 <= s <= 10^9)$

第二行是 $M$ 个整数，表示已集满能源仓的坐标序列，其中每个 $xi$ 表示坐标 $(0<=x_i<=10^9)$

第三行是 $M$ 个整数，是已集满能源仓的存储能量序列，其中每个 $c_i$ 表示 $x_i$ 处对应能源仓存储了多少单位的能源 $(1<=c_i<=10000)$

输出描述

每组数据输出一个结果，每个结果占一行

补充说明

对于 $20$% 的数据: $0 <= N<= 5000,1<= M<= 2000,0 <=x_i, s<=10^6$

对于 $100$% 的数据: $0<=N<=10^9,1<=M<=100000,0<=x_i,s<= 10^9$

对手同一组测试数据所有 $x_i$ 两两不同

样例1

输入

1
4 3 5
8 4 6
4 7 2

输出

9

说明

从起点坐标 $5$ 出发，可以先到坐标 $4$，再到坐标 $6$。共消耗 $1+2=3$ 单位燃料，可以完成这两个能源仓的转运任务，转运总量为 $7 + 2 = 9$。

如果在这之后还想继续前往坐标 $8$，还需要额外消耗 $2$ 单位燃料，总消耗会变成 $5$，超过限制，因此答案为 $9$。

样例2

输入

1
5 4 5
8 1 6 4
9 3 5 8

输出

22

说明

从起点坐标 $5$ 出发，可以先到坐标 $4$，再到坐标 $6$，最后到坐标 $8$。共消耗 $1+2+2=5$ 单位燃料，可以完成这三个能源仓的转运任务，转运总量为 $8+5+9=22$。

如果还想再前往坐标 $1$，所需燃料至少为 $10$，超过限制，因此答案为 $22$。

样例3

输入

1
9 7 10
4 13 9 11 6 15 8
10 8 4 7 9 11 5

输出

35

说明

从起点坐标 $10$ 出发，可以先到坐标 $11$，再依次前往坐标 $9、8、6、4$。共消耗 $1+2+1+2+2=8$ 单位燃料，可以完成这五个能源仓的转运任务，转运总量为 $7+4+5+9+10=35$。

如果还想再前往坐标 $13$，所需燃料至少为 $12$；如果还想再前往坐标 $15$，所需燃料至少为 $16$，都会超出限制，因此答案为 $35$。