Đà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í Xi, X2, X3,... Xn 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: 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í Xi (0 ≤ Xi ≤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í X1 = 11

Input 02:

6 2
2
20
6
5
4
17

Output 02:

2

Giải thích: Với lực đập R=2, người chơi có thể đào 2 lần ở vị trí X1 = 4 và X2 = 18