#374. 爆破大师

传统 200 ms 256 MiB
标准 IO
文本比较 admin 标签

题目描述

nn 个爆破大师,他们正在处理 mm 个爆破任务。

爆破大师的位置和爆破任务的位置均可以用一个一维坐标描述,从 xx 走到 yy 需要花费 xy|x-y| 的时间。

忽略执行爆破任务的时间,请给每一个爆破大师安排一个执行计划,完成所有任务所需的时间最少。

注意 nn 个爆破大师是同时在执行任务的,完成任务的时间是最慢的任务被完成的时间。

输入格式

第一行一个整数 TT 表示数据组数。

每组数据 33 行:

第一行两个正整数 n,mn,m

然后一行 nn 个正整数 xix_i ,表示每一个爆破大师的位置。

然后一行 mm 个正整数 yiy_i ,表示每一个爆破任务的位置。

输出格式

每组数据输出一行表示最小的时间。

样例

样例输入

2
3 4
2 5 6
1 3 6 8
1 2
3
1 4

样例输出

2
4

数据范围与提示

T20,1n,m20000,0xi,yi108,xixi1,yiyi1T\leq 20,1\leq n,m\leq 20000,0\leq x_i,y_i\leq 10^8,x_i\ge x_{i-1},y_i\ge y_{i-1}

保证 n>2000n>2000 的数据不超过44组。