3294. WiFi

单点时限: 3.0 sec

内存限制: 512 MB

章鱼王沿着国王大道巡视着他强大的王国,国王大道可以被看做一条直线,章鱼王的城堡的位置是 $0$。

章鱼王知道他的国家里有 $n$ 个 WiFi 信号发射器,第 $i$ 个发射器在 $a_i$ 位置,代表章鱼王城堡向东 $a_i$ 米(若 $a_i<0$ 则为向西),WiFi 的强度为 $b_i$,代表 $a_i$ 处能接收到强度为 $b_i$ 的信号,而与信号发射器距离每增加 $1$ 米,信号强度就减少 $1$,直到信号为 $0$ 就不再减少。

章鱼王有 $q$ 个询问,他想知道在国王大道 $c_i$ 位置处能接收到的最大信号强度。

输入格式

第一行为数据组数 $T$ $(T\leq 10)$。

每组数据第一行为 $n,q$ ,第二行为 $n$ 个数字 $a_i$,第三行为 $n$ 个数字 $b_i$,接下来一行 $q$ 个询问 $c_i$。

保证 $40\%$ 的数据满足:$1\leq n,q\leq 1000$。

保证 $100\%$ 的数据满足:$1\leq n,q\leq 10^5, 0\leq |a_i|\leq 10^9,0\leq b_i\leq 10^9,0\leq |c_i|\leq 10^9$。

所有数均为整数。

输出格式

对于每组数据中的每个询问,输出一行结果。

样例

Input
1
2 3
0 6
3 6
0 -1 5
Output
3
2
5

6 人解决,20 人已尝试。

7 份提交通过,共有 80 份提交。

8.4 EMB 奖励。

创建: 3 年前.

修改: 2 年,10 月前.

最后提交: 1 年,10 月前.

来源: 2017.7.1 少年宫暑假摸底

题目标签