Đà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ố đị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ườ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 trước được đào tối đa ~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 ~R~ 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 từ file văn bản DAOVANG.INP, 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 vàng tối đa. Dòng thứ ~i~ trong ~N~ dòng tiếp theo cho biết vị trí ~X_i~ ~(0 \le X_i \le 10^6)~ của thỏi vàng thứ ~i~.

Kết quả

Ghi ra file văn bản DAOVANG.OUT 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 tương ứng với ~20\%~ số điểm của bài có ~K = 1~ và ~N \le 1 000~.
• ~20\%~ test tương ứng với ~20\%~ số điểm của bài có ~K = 2~ và ~N \le 10 000~.
• ~60\%~ test tương ứng với ~60\%~ số điểm của bài có ~K \le 20~ và ~N \le 50 000~.

Ví dụ 1

Dữ liệu

6 1
2
20
6
5
4
17

Kết quả

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~.

Ví dụ 2

Dữ liệu

6 2
2
20
6
5
4
17

Kết quả

2

Giải thích

Với lực đập ~R = 2~, người chơi có thể đào ~2~ lần ở vị trí ~X_1 = 4~ và ~X_2 = 18~.