문제

은영이는 도로를 따라 늘어선 $N$개의 창고를 관리하고 있다. ($1 ≤ N ≤ 5 ∙ 10^4$) $i$번째 창고에는 $a_i$개의 건초 더미와 $b_i$개의 사료 가방이 들어 있다. ($0 ≤ a_i, b_i ≤ 10^9$)

준모는 창고들 사이의 불평등함에 대해 불만을 가지고 있다. 준모는 농장의 "불균형"을 모든 창고의 건초 개수 중 최댓값과 모든 창고의 사료 개수 중 최솟값의 차이로 정의한다. 엄밀하게 말하면, 불균형은 $\max(a) - \min(b)$이다.

준모의 불만을 해결하기 위해 은영이는 정확히 $K$번의 작업을 수행할 수 있다. ($1 ≤ K ≤ 10^{18}$) 각 작업에서 은영이는 창고 하나를 선택하여 건초 더미 하나를 팔고, 그 창고를 위해 사료 가방 하나를 새로 산다. 은영이는 빚을 지는 것을 두려워하지 않으므로 물건의 개수가 음수가 되어도 상관없다. 즉, 매번 인덱스 $i \in [1, N]$를 하나 골라 $a_i$를 $1$ 감소시키고 $b_i$를 $1$ 증가시키는 과정을 정확히 $K$번 수행한다.

정확히 $K$번의 작업을 수행한 후 가능한 불균형의 최솟값을 구하시오.

입력

첫째 줄에 독립적인 테스트 케이스의 개수 $T$가 주어진다. ($1 \le T \le 1\,000$)

각 테스트 케이스의 첫째 줄에는 $N$과 $K$가 공백으로 구분되어 주어진다. ($1 \le N \le 5 \cdot 10^4$; $1 \le K \le 10^{18}$)

둘째 줄에는 각 창고의 건초 개수 $a_1, \dots, a_N$이 공백으로 구분되어 주어진다.

셋째 줄에는 각 창고의 사료 개수 $b_1, \dots, b_N$이 공백으로 구분되어 주어진다.

모든 테스트 케이스에 대해 $N$의 합은 $5 \cdot 10^4$을 넘지 않는다.

출력

각 테스트 케이스마다 정확히 $K$번의 작업을 수행한 후 $\max(a) - \min(b)$의 최솟값을 한 줄에 하나씩 출력한다.

예제 입력 1

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

예제 출력 1

-18
90
0
0

제한

• 테스트 케이스 2~4: $K \le 500$, 모든 테스트 케이스의 $N$의 합 $\le 500$
• 테스트 케이스 5~8: 모든 테스트 케이스의 $N$의 합 $\le 500$
• 테스트 케이스 9~13: 추가적인 제한 사항이 없다.