Dà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 đượ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 đầ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 \le X_{i} \le 10^9)~ của thỏi vàng thứ ~i~.

Dữ liệu đầu ra

Gồm 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 dữ liệu

• 20% test ứng với 20% số điểm của bài có ~K = 1~ và ~N \le 1000~;
• 20% test ứng với 20% số điểm của bài có ~K = 2~ và ~N \le 10000~;
• 60% test ứng với 60% số điểm của bài có ~K \le 20~ và ~N \le 50000~;

Ví dụ

Ví dụ 1

INPUT

6 1
2
20
6
5
4
17

OUTPUT

9

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

Ví dụ 2

INPUT

6 2
2
20
6
5
4
17

OUTPUT

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