Optimal Arsenal Calibration

Bạn nhận được một công việc tại một studio trò chơi phát triển game bắn súng trực tuyến, và nhiệm vụ lớn đầu tiên của bạn là hỗ trợ cân bằng vũ khí. Trò chơi có $n$ vũ khí: khẩu súng thứ $i$ có tốc độ bắn là số nguyên $f_i$ và sát thương mỗi viên đạn là số nguyên $d_i$. Tổng hỏa lực của khẩu súng thứ $i$ bằng $p_i = f_i · d_i$.

Bạn cần điều chỉnh giá trị $d_i$ của một số khẩu súng sao cho các giá trị $d_i$ mới vẫn là các số nguyên, đồng thời hỏa lực của tất cả các khẩu súng đạt trạng thái cân bằng. Với một số nguyên $k$ cho trước, các khẩu súng được coi là cân bằng nếu $\max\limits_{1 ≤ i ≤ n}{p_i} - \min\limits_{1 ≤ i ≤ n}{p_i} ≤ k$.

Vì người chơi không thích những thay đổi quá lớn, bạn cần thay đổi giá trị $d_i$ của ít khẩu súng nhất có thể. Hãy tìm số lượng khẩu súng tối thiểu cần thay đổi các giá trị này để các khẩu súng trở nên cân bằng.

Lưu ý rằng các giá trị $d_i$ mới phải là các số nguyên lớn hơn $0$.

Dữ liệu vào

Dòng đầu tiên chứa một số nguyên $t$ ($1 ≤ t ≤ 1000$): số lượng bộ dữ liệu.

Dòng đầu tiên của mỗi bộ dữ liệu chứa hai số nguyên $n$ và $k$ ($2 ≤ n ≤ 3000$, $0 ≤ k ≤ 1500$): số lượng khẩu súng cần cân bằng và độ chênh lệch tối đa cho phép giữa khẩu súng mạnh nhất và khẩu súng yếu nhất.

Dòng thứ hai của mỗi bộ dữ liệu chứa $n$ số nguyên $f_1, f_2, ..., f_n$ ($1 ≤ f_i ≤ 2000$), trong đó $f_i$ là tốc độ bắn của khẩu súng thứ $i$.

Dòng thứ ba của mỗi bộ dữ liệu chứa $n$ số nguyên $d_1, d_2, ..., d_n$ ($1 ≤ d_i ≤ 10^9$), trong đó $d_i$ là sát thương mỗi viên đạn của khẩu súng thứ $i$.

Tổng của $n$ trên tất cả các bộ dữ liệu được bảo đảm không vượt quá $3000$ ($\sum n ≤ 3000$).

Kết quả

Với mỗi bộ dữ liệu, in ra một số nguyên duy nhất: số lượng khẩu súng tối thiểu cần thay đổi sát thương $d_i$ để các khẩu súng đạt trạng thái cân bằng.

Chấm điểm

Subtask 1 (20 points). $f_i ≤ k$ với mọi $1 ≤ i ≤ n$

Subtask 2 (20 points). $k = 0$

Subtask 3 (60 points). $1 ≤ t ≤ 1000$; $2 ≤ n ≤ 3000$; $\sum n ≤ 3000$

Ví dụ

Input

5
4 2
6 3 13 7
1 2 1 2
3 2
100 101 102
100 99 98
5 0
1 12 4 4 3
12 1 3 3 4
2 50
1000 10
1000000000 1
3 5
1 19 11
49 4 72

Output

2
3
0
1
2

Ghi chú

Trong bộ dữ liệu đầu tiên, bạn có thể đặt $d_1 = 2$ và $d_2 = 4$. Khi đó, mảng sát thương sẽ là $d = [2, 4, 1, 2]$, và các giá trị hỏa lực tương ứng sẽ là $p = [12, 12, 13, 14]$. Các khẩu súng đạt trạng thái cân bằng vì $14 - 12 ≤ 2$.

Trong bộ dữ liệu thứ hai, bạn phải thay đổi giá trị $d_i$ của cả ba khẩu súng. Ví dụ, bạn có thể đặt $d = [5151, 5100, 5050]$.

Trong bộ dữ liệu thứ ba, tất cả các khẩu súng đã ở trạng thái cân bằng sẵn, do đó bạn không cần thay đổi giá trị nào.