Hành lang tầng 3 nhà A1 là một đoạn thẳng dài, dọc theo đó có ~n~ ổ cắm điện. Coi hành lang là một trục số, ổ cắm thứ ~i~ nằm tại toạ độ nguyên ~x_i~; không có hai ổ cắm nào cùng toạ độ.

Trung tâm Công nghệ thông tin cần lắp ~k~ bộ phát Wi-Fi, mỗi bộ phải cắm vào một ổ cắm và mỗi ổ cắm chỉ cắm được một bộ. Hai bộ phát đặt quá gần nhau sẽ gây nhiễu sóng, vì vậy kỹ thuật viên muốn khoảng cách nhỏ nhất giữa hai bộ phát bất kỳ là lớn nhất có thể. Khoảng cách giữa hai bộ phát đặt tại toạ độ ~p~ và ~q~ là ~|p - q|~.

Yêu cầu

Hãy chọn ra ~k~ ổ cắm để lắp ~k~ bộ phát sao cho khoảng cách nhỏ nhất giữa hai bộ phát bất kỳ đạt giá trị lớn nhất, và in ra giá trị đó.

Dữ liệu vào

• Dòng thứ nhất chứa hai số nguyên ~n~ và ~k~;
• Dòng thứ hai chứa ~n~ số nguyên ~x_1, x_2, \ldots, x_n~, các số cách nhau bởi dấu cách. Các toạ độ không nhất thiết được cho theo thứ tự tăng dần.

Kết quả ra

Ghi ra một số nguyên duy nhất là giá trị lớn nhất có thể của khoảng cách nhỏ nhất giữa hai bộ phát.

Ràng buộc

~2 \le k \le n \le 2 \cdot 10^5~; ~0 \le x_i \le 10^9~; các ~x_i~ đôi một khác nhau.

• Subtask 1 (15% số điểm – test 01–03): ~n \le 15~;
• Subtask 2 (20% số điểm – test 04–07): ~k = 2~;
• Subtask 3 (25% số điểm – test 08–12): ~n \le 2000~ và ~x_i \le 10^4~;
• Subtask 4 (40% số điểm – test 13–20): không có ràng buộc bổ sung.

Ví dụ

Dữ liệu vào mẫu 1

5 3
1 2 8 4 9

Kết quả ra mẫu 1

3

Giải thích

Cần lắp ~3~ bộ phát vào ~5~ ổ cắm tại các toạ độ ~1, 2, 4, 8, 9~. Chọn các ổ cắm tại toạ độ ~1~, ~4~ và ~8~: ba khoảng cách đôi một là ~3~, ~4~ và ~7~, nhỏ nhất bằng ~3~. Không có cách chọn nào đạt khoảng cách nhỏ nhất từ ~4~ trở lên: muốn vậy ba bộ phát phải trải trên một đoạn dài ít nhất ~8~, tức là phải dùng hai ổ cắm ở toạ độ ~1~ và ~9~, nhưng khi đó bộ phát ở giữa phải cách cả hai đầu ít nhất ~4~, tức là phải nằm đúng toạ độ ~5~ – nơi không có ổ cắm.