John Nông Dân có \(N\) (\(1\le N\le 5\cdot 10^4\)) nhà kho nằm dọc theo một con đường. Nhà kho thứ \(i\) chứa \(a_i\) kiện cỏ khô và \(b_i\) bao thức ăn \((0\le a_i,b_i\le 10^9)\).

Bessie phàn nàn về sự bất bình đẳng giữa các nhà kho. Cô định nghĩa "độ mất cân bằng" của trang trại là hiệu giữa lượng cỏ khô lớn nhất trong một nhà kho bất kỳ và lượng thức ăn nhỏ nhất trong một nhà kho bất kỳ. Nói một cách chính thức, độ mất cân bằng là \(\max(a) - \min(b)\).

Để giải quyết mối lo của Bessie, John Nông Dân có thể thực hiện đúng \(K\) (\(1\le K\le 10^{18}\)) lần chuyển đổi. Trong mỗi lần chuyển đổi, ông chọn một nhà kho \(i\), bán một kiện cỏ khô của nhà kho đó và mua một bao thức ăn mới cho chính nhà kho ấy. Lưu ý rằng các lượng trong trang trại có thể âm (ông không ngại mắc nợ). Nói một cách chính thức, lặp lại \(K\) lần: chọn một chỉ số \(i\in [1,N]\), giảm \(a_i\) đi một và tăng \(b_i\) lên một.

Hãy giúp John Nông Dân xác định độ mất cân bằng nhỏ nhất có thể sau khi thực hiện đúng \(K\) lần chuyển đổi.

Dữ liệu vào

Dòng đầu tiên chứa \(T\) (\(1 \leq T \leq 10^3\)), số lượng bộ test độc lập.

Dòng đầu tiên của mỗi bộ test chứa \(N\) và \(K\).

Dòng tiếp theo chứa \(a_1\dots a_N\).

Dòng tiếp theo chứa \(b_1\dots b_N\).

Tổng \(N\) trên tất cả các bộ test không vượt quá \(5 \cdot 10^4\).

Dữ liệu ra

Với mỗi bộ test, in ra một số nguyên duy nhất là giá trị nhỏ nhất có thể của \(\max(a) - \min(b)\) sau khi thực hiện \(K\) lần chuyển đổi.

Ví dụ

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

-18
90
0
0

Phân nhóm

• Các test 2–4: \(K\le 500\), tổng \(N\) trên tất cả các bộ test không vượt quá \(500\).
• Các test 5–8: Tổng \(N\) trên tất cả các bộ test không vượt quá \(500\).
• Các test 9–13: Không có ràng buộc bổ sung.

Nguồn

USACO 2026 Contest 2, Gold Division — Balancing the Barns. Tác giả: Rohin Garg.
https://usaco.org/index.php?page=viewproblem2&cpid=1569