Những con bò hung hăng (Aggressive Cows)

Nguồn: SPOJ

Phiên bản: Phước Hưng OJ Extended

Đề bài

Có $N$ chuồng nằm trên một đường thẳng tại các tọa độ $x_i$. Cần đặt $C$ con bò vào $C$ chuồng khác nhau.

Nếu các vị trí được chọn là $p_1,p_2,\ldots,p_C$, giá trị của một cách đặt là:

Hãy tìm giá trị lớn nhất có thể của đại lượng này.

Input

Dòng đầu chứa $N,C$. $N$ dòng tiếp theo chứa tọa độ các chuồng.

Output

In giá trị lớn nhất có thể của khoảng cách nhỏ nhất giữa hai con bò.

Subtask

• Subtask 1 — 20%: $C=2$.
• Subtask 2 — 30%: $2\le N\le2000$.
• Subtask 3 — 50%: $2\le N\le10^5$, $2\le C\le N$, $0\le x_i\le10^9$.

Ví dụ

Input

5 3
1
2
8
4
9

Output

3

Giải thích

Sau khi sắp xếp các chuồng thành $1,2,4,8,9$, có thể đặt bò tại $1,4,8$. Khoảng cách nhỏ nhất là $3$ và không thể tăng lên $4$.