Đà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 hà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.

Input

• Dòng đầu chứa \(2\) 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\).

Output

• Một số nguyên là giá trị lực đập \(R\) bé nhất để lấy được \(N\) thỏi vàng tối đa sau \(K\) lần đào.

Scoring

• 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\)

Input 1

6 1
2
20
6
5
4
17

Output 1

9

Input 2

6 2
2
20
6
5
4
17

Output 2

2

Note

• Giải thích ví dụ \(1\):
• Với lực đập \(R = 9\), người chơi có thể đào 1 lần ở vị trí \(X_1 = 11\)
• 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\)