Bài 4

Trong tựa game chiến thuật "Đế Chế Cổ Đại", bạn đóng vai một vị tướng quân đang thiết lập một tuyến phòng thủ dọc theo biên giới. Trên tuyến đường biên giới thẳng tắp này, có sẵn $N$ vị trí bằng phẳng khác nhau có thể dùng để xây dựng thành lũy. Tuy nhiên, tài nguyên hiện tại chỉ đủ để bạn xây dựng đúng $K$ thành lũy ($K < N$), mỗi thành lũy được xây trên một vị trí. Giá trị khoảng cách giữa hai thành lũy gần nhau tương ứng với mức chênh lệch giá trị của hai vị trí đó.

Kẻ thù trong game sở hữu những cỗ máy bắn đá có khả năng sát thương diện rộng. Để giảm thiểu thiệt hại, tránh việc một lần bắn mà đá đập trúng nhiều thành lũy cùng lúc, bạn cần phải bố trí $K$ thành lũy này sao cho khoảng cách gần nhất giữa hai thành lũy bất kỳ cần phải càng xa càng tốt.

Yêu cầu: Cho $N$ vị trí trên bản đồ và $K$ vị trí để xây thành lũy. Tìm giá trị $X$ sao cho $X$ là lớn nhất trong số các khoảng cách gần nhau nhất giữa hai thành lũy bất kỳ.

Đọc từ tệp văn bản BAI4.INP:

• Dòng đầu tiên chứa hai số nguyên dương $N$ và $K$ ($2 \le K < N$).
• Dòng thứ hai chứa $N$ số nguyên dương $A_1, A_2, \dots, A_N$ ($0 \le A_i \le 10^9$) là các vị trí cần xây dựng. Các vị trí này chưa sắp xếp.

Ghi ra tệp văn bản BAI4.OUT giá trị của $X$.

• Subtask 1 (40% số điểm): $N \le 100$.
• Subtask 2 (60% số điểm): $N \le 10^5$.