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
历年学员USACO获奖战绩一览
USACO 历年战绩
2026赛季战绩
- 5位铂金级
- 22位金级
- 25位银级
2024–2025赛季战绩
翰林考点及辅导学生
- 5位铂金级
- 25位金级
- 38位银级
2023–2024赛季战绩
- 8位铂金级
- 32位金级
- 37位银级
2022–2023赛季战绩
- 10位铂金级
- 29位金级
- 71位银级
篇幅有限,仅展示部分年份战绩。
