样例下载

题目描述

有一个 $2$ 行 $N$ 列的矩阵 $A$，该矩阵有一个属性值，定义为 “第一行所有数的最大值” 减去 “第二行所有数的最小值” 的差。

你希望调整矩阵的属性值使其尽可能小。为此，你决定进行恰好 $M$ 次操作。

每次操作，你可以选中任意一列 $j$，将该列中上面的数即 $A_{1,j}$ 减一，下面的数即 $A_{2,j}$ 加一。

问：如何操作，可以使得矩阵的属性值尽可能小？你只需要输出可以得到的最小属性值。

多组数据。

输入格式

第一行：一个整数 $T$，表示数据组数。

对于每组数据：

• 第一行：两个整数 $N, M$。
• 接下来两行，每行 $N$ 个数，用来描述矩阵 A。

数据保证所有组数据的 $\sum N ≤ 5·10^4$。

输出格式

共 T 行，每组数据的答案占一行。

样例输入

3
1 5
0
0
2 5
10 9
1 2
3 3
1 2 1
0 1 0

样例输出

-10
3
0

数据范围

• 40% 的数据：所有组数据的 $\sum N ≤ 500$，其中有一半的数据 $M ≤ 500$，

• 100% 的数据：$1 ≤ T ≤ 10^3$, $1 ≤ N ≤ 5·10^4$, $0 ≤ A_{ij} ≤ 10^9$, $1 ≤ M ≤ 10^{18}$