Farmer John has () barns arranged along a road. The -th barn contains bales of hay and bags of feed ).
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 .
To address Bessie's concerns, Farmer John can perform exactly () transfers. In each transfer, he selects a barn , 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, times, you choose an index , decrement , and increment .
Help Farmer John determine the minimum possible imbalance after performing exactly transfers.
输入格式
The first line contains (), the number of independent test cases.
The first line of each test case contains and .
The following line contains .
The following line contains .
The sum of over all test cases is at most .
输出格式
For each test case, output a single integer, the minimum possible value of after performing operations.
In the first test case, Farmer John can transfer haybales from barn into bags of feed. This leaves and . The imbalance is .
In the second test case, Farmer john can transfer haybales from barn and haybale from barn . This leaves and . The imbalance is . This is the minimum imbalance Farmer John can achieve.
