Nhiệt Độ Phòng

Một văn phòng có \(N\) nhân viên, đánh số từ \(1\) đến \(N\). Khi không mặc áo khoác, nhiệt độ thích hợp của
nhân viên thứ \(i\) là \(A_i\) độ. Mỗi khi mặc thêm một áo khoác, nhiệt độ thích hợp của người đó giảm đi
\(T\) độ: nếu nhân viên \(i\) mặc \(k\) áo khoác (\(k\) là số nguyên không âm tuỳ ý người đó chọn), nhiệt độ
thích hợp của họ lúc đó là \(A_i - k \cdot T\) độ.

Khi nhiệt độ phòng được đặt là \(x\) độ và nhiệt độ thích hợp hiện tại của một nhân viên là \(y\) độ, độ khó
chịu của người đó là \(|x - y|\). Mỗi nhân viên sẽ tự chọn số áo khoác của mình (có thể không mặc) để độ
khó chịu của họ là nhỏ nhất có thể, ứng với nhiệt độ phòng \(x\) đã cho.

Gọi độ khó chịu của phòng là giá trị lớn nhất trong số các độ khó chịu của tất cả nhân viên. Ban
quản lý muốn chọn một nhiệt độ phòng \(x\) (là số nguyên, có thể âm) sao cho độ khó chịu của phòng là nhỏ
nhất. Hãy tính giá trị nhỏ nhất đó của độ khó chịu phòng.

Input

• Dòng đầu tiên chứa hai số nguyên \(N\) và \(T\) (\(2 \le N \le 500000\), \(1 \le T \le 10^9\)).

• Dòng thứ hai chứa \(N\) số nguyên \(A_1, A_2, \ldots, A_N\) (\(1 \le A_i \le 10^9\)).

Ràng buộc:

• Subtask 1 (15 điểm): \(N = 2\).

• Subtask 2 (5 điểm): \(N \le 3000\), \(T = 1\).

• Subtask 3 (30 điểm): \(N \le 3000\), \(T \le 2\).

• Subtask 4 (35 điểm): \(N \le 3000\), \(T \le 3000\).

• Subtask 5 (15 điểm): Không có ràng buộc bổ sung.

Output

In ra một dòng duy nhất chứa một số nguyên là độ khó chịu nhỏ nhất của phòng có thể đạt được.

Example 1

Input:

2 4
19 24

Output:

1

Example 2

Input:

3 1
21 19 23

Output:

0

Example 3

Input:

6 8
24 22 21 25 29 17

Output:

2

Note

Trong ví dụ thứ nhất, nếu đặt nhiệt độ phòng là \(16\) độ: nhân viên \(1\) mặc \(1\) áo khoác, nhiệt độ thích
hợp trở thành \(19 - 1 \cdot 4 = 15\) độ, độ khó chịu là \(|16 - 15| = 1\); nhân viên \(2\) mặc \(2\) áo khoác,
nhiệt độ thích hợp trở thành \(24 - 2 \cdot 4 = 16\) độ, độ khó chịu là \(0\). Độ khó chịu của phòng khi đó là
\(1\), và không có cách chọn \(x\) nào cho độ khó chịu nhỏ hơn.