Angry Bird là một chiếc game độc quyền mà ở đó người chơi dùng súng cao su bắn những con chim vào một cảnh một chiều bao gồm một tập hợp các đàn heo nằm ở nhiều điểm khác nhau trên một trục số. Mỗi con chim sau khi bắn sẽ tiếp đất với một lực đủ mạnh để làm nổ các con heo ở gần nơi nó hạ cánh. Mục tiêu là sử dụng một đàn chim để kích nổ tất cả các con heo.

Có \(N\) con heo được đặt ở các tọa độ \(x_1, x_2,...,x_N\) phân biệt trên trục số. Nếu con chim được bắn với lực \(R\) và đáp đất ở vị trị \(x\), vụ nổ diễn ra trong bán kính \(R\), kích nổ tất cả các con heo trong tầm \([x - R, x + R]\).

Tổng cộng có \(K\) con chim đang sẵn sàng để bắn, mỗi con chim đêu bắn với lực \(R\). Hãy xác định giá trị nhỏ nhất của \(R\) để kích nổ được hết tất cả con heo.

Input

• Dòng đầu gồm 2 số nguyên \(N, K (0 <N \leq 5\times 10^4, K \leq 10^5)\) lần lượt là số lượng con heo và số lượng con chim.
• \(N\) dòng tiếp theo, dòng thứ \(i\) là số nguyên \(a_i (0 \leq a_i ≤ 10^9)\) là vị trí của con heo thứ \(i\).

Output

Kết quả: Một số duy nhất là số \(R\) tìm được.

Example

7 2
20
25
18
8
10
3
1

5