Đào vùng là trò chơi khá phổ biến và có nhiều phiên bản. Hãy cùng xét một phiên bản cửa trò chơi này. Có N thơi vùng được cố dịnh ở các vị trí ~X_1, X_2, X_3,... X_n~ trên một trục nằm ngang. Nếu ngưrời chơi đào ở vị trí X với máy khoan có lực đập R thì có thể lấy được các thỏi vàng cách vị trí X tối đa R đơn vị chiều dài hay các thỏi vàng có vị trí nằm trong khoảng [X-R; X+R]. Người chơi được đào tối da K lần và lực đập R là giống nhau ở các lần đào. Nếu người chơi chọn lực đập K càng nhỏ thì số điểm đạt được càng cao và ngược lại. Người chơi được thực hiện tổi đa K lần đào, hãy giúp người chơi chọn lực đập R nhỏ nhất để có thể đào hết N thỏi vàng.

Yêu cầu: Cho trước vị trí của N thỏi vàng, hãy viết chương trình tìm giá trị nguyên R bé nhất sao cho người chơi có thể lấy được N thỏi vàng sau tối đa K lần đào.

*Dữ liệu vào: *

Dòng đầu chứa hai số nguyên N và K lần lượt cho biết số lượng thỏi vàng và số lần đào tối đa.

Dòng thứ i trong N dòng tiếp theo cho biết vị trí ~X_i (0 ≤ X_i ≤10^9)~ của thỏi vàng thứ i.

Kết quả: In ra một số nguyên là giá trị lực đập R bé nhất để lấy được N thỏi vàng sau tối đa K lần đào.

Ràng buộc:

• 20% test ứng với 20% số điểm của bài có K = 1 và N ≤ 1000

• 20% test ứng với 20% số điểm của bài có K = 2 và N ≤ 10000

• 60% test ứng với 60% số điểm của bài có K ≤ 20 và N ≤50000

Ví dụ:

Input 01:

6 1

2

20

6

5

4

17

Output 01:

9

Giải thích: Với lực đập R=9, người chơi có thể đào 1 lần ở vị trí ~X_1 = 11~

Input 02: 6 2

2

20

6

5

4

17

Output 02:

2