Chủ tịch K chịu trách nhiệm điều chỉnh nhiệt độ của căn phòng nơi các cán bộ đang làm việc. Ông muốn mọi người cảm thấy thoải mái nhất có thể.

Hiện có \(N\) cán bộ trong phòng, được đánh số từ \(1\) đến \(N\). Khi không mặc áo khoác, nhiệt độ thích hợp với cán bộ \(i\) (\(1 \le i \le N\)) là \(A_i\) độ. Với mỗi người, mỗi khi mặc thêm một chiếc áo khoác, nhiệt độ thích hợp giảm đi \(T\) độ. Nói cách khác, khi cán bộ \(i\) mặc \(k\) chiếc áo khoác, nhiệt độ thích hợp với người đó là \(A_i-kT\) độ.

Khi nhiệt độ phòng là \(x\) độ và nhiệt độ thích hợp với một cán bộ là \(y\) độ, độ khó chịu của người đó là \(|x-y|\), trong đó \(|t|\) là giá trị tuyệt đối của \(t\). Tùy theo nhiệt độ phòng, mỗi cán bộ tự chọn số áo khoác cần mặc, là một số nguyên không âm, để độ khó chịu của mình nhỏ nhất.

Chủ tịch K gọi giá trị lớn nhất trong các độ khó chịu của mọi cán bộ là độ khó chịu của căn phòng. Ông muốn chọn nhiệt độ phòng sao cho giá trị này nhỏ nhất. Nhiệt độ phòng được chọn phải là một số nguyên.

Cho thông tin về các cán bộ và nhiệt độ thích hợp, hãy tìm độ khó chịu nhỏ nhất có thể của căn phòng.

Dữ liệu vào

Dữ liệu được cho từ đầu vào chuẩn theo dạng:

N T
A_1 A_2 ... A_N

Dữ liệu ra

In ra một dòng chứa độ khó chịu nhỏ nhất có thể của căn phòng.

Ràng buộc

• \(2 \le N \le 500\,000\).
• \(1 \le T \le 10^9\).
• \(1 \le A_i \le 10^9\) (\(1 \le i \le N\)).
• Tất cả các giá trị đầu vào đều là số nguyên.

Phân nhóm

1. 15 điểm: \(N=2\).
2. 5 điểm: \(N \le 3\,000\), \(T=1\).
3. 30 điểm: \(N \le 3\,000\), \(T \le 2\).
4. 35 điểm: \(N \le 3\,000\), \(T \le 3\,000\).
5. 15 điểm: Không có ràng buộc bổ sung.

Ví dụ

2 4
19 24

1

3 1
21 19 23

0

6 8
24 22 21 25 29 17

2

Nguồn

Room Temperature, JOI 2024, vòng chung kết quốc gia, bài 1 (tiếng Anh) · Đề tiếng Nhật. Tác giả: Ủy ban Olympic Tin học Nhật Bản. Đề gốc và bản dịch được cung cấp theo giấy phép CC BY-SA 4.0.