Farmer John has N (1≤N≤5⋅104) barns arranged along a road. The i-th barn contains ai bales of hay and bi bags of feed (0≤ai ,bi ≤109).
Bessie has been complaining about the inequality between barns. She defines the "imbalance" of the farm as the difference between the maximum hay in any barn and the minimum feed in any barn. Formally, the imbalance is max(a)−min(b).
To address Bessie's concerns, Farmer John can perform exactly K (1≤K≤1018 ) transfers. In each transfer, he selects a barn i, sells one of its haybales, and buys it a new bag of feed for the same barn. Note that there can be negative amounts in his farm (he is not afraid of debt). Formally, K times, you choose an index i∈[1,N], decrement ai, and increment bi .
Help Farmer John determine the minimum possible imbalance after performing exactly K transfers.
INPUT FORMAT (input arrives from the terminal / stdin):
The first line contains T (1≤T≤103), the number of independent test cases.
The first line of each test case contains Nand K.
The following line contains a1…aN.
The following line contains b1…bN.
The sum of N over all test cases is at most 5⋅104 .
OUTPUT FORMAT (print output to the terminal / stdout):
For each test case, output a single integer, the minimum possible value of max(a−min(b) after performing K operations.
SAMPLE INPUT:
4
1 10
5
3
2 6
100 96
0 4
3 3
1 1 2
0 0 1
3 3
1 2 2
0 1 1
SAMPLE OUTPUT:
-18
90
0
0
In the first test case, Farmer John can transfer 10 haybales from barn 1 into bags of feed. This leaves a=[−5] and b=[13]. The imbalance is max(a−min(b)=−5−13=−18.
In the second test case, Farmer john can transfer 5 haybales from barn 1 and 1 haybale from barn 2. This leaves a=[95,95] and b=[5,5]. The imbalance is 95−5=90. This is the minimum imbalance Farmer John can achieve.
SCORING:
Inputs 2-4: K≤500, sum of N over all testcases is ≤500
Inputs 5-8: Sum of N over all testcases is ≤500
Inputs 9-13: No additional constraints.
Problem credits: Rohin Garg