Ngày xửa ngày xưa, xưa ơi là xưa, buitrunghieu là một bom thủ có tiếng trong giới bom thủ. Những quả bom của anh ta rất mạnh, mạnh đến mức đủ mạnh để làm nổ những quả bom xung quanh quả bom vừa phát nổ.

Có \(N (2 ≤ N ≤ 5.10^4)\) quả bom nằm ở các vị trí số nguyên riêng biệt \(x_1, x_2, ..., x_N (x_i ≤ 10^9 )\) trên dãy số. Nếu một quả bom được kích nổ với sức mạnh \(R\) tại vị trí \(x\), điều này sẽ gây ra một vụ nổ có "bán kính R", bao trùm tất cả các quả bom trong khoảng từ \(x-R\) đến \(x+R\).

Tổng cộng \(K\) quả bom có sẵn để kích nổ, mỗi con có cùng sức mạnh \(R\). Vui lòng xác định giá trị số nguyên nhỏ nhất của \(R\) sao cho có thể sử dụng \(K\) quả bom để kích nổ tất cả các quả bom hiện tại.

INPUT FORMAT

Dòng đầu tiên của đầu vào chứa \(N\) và \(K (K ≤ 10)\).

N dòng còn lại chứa các số nguyên \(x_1, x_2, ..., x_N\).

OUTPUT FORMAT

Hãy xuất ra số nguyên \(R\) là sức mạnh tối thiểu để kích nổ tất cả.

Ví dụ:

Input

7 2
20
25
18
8
10
3
1

Ouput

5