Aggressive Cows

Source: SPOJ

Version: Phuoc Hung OJ Extended

Problem Statement

There are $N$ stalls on a line at positions $x_i$. Place $C$ cows in distinct stalls. If the selected positions are $p_1,p_2,\ldots,p_C$, the value of the placement is

Find the maximum possible value.

Input

The first line contains $N,C$. The next $N$ lines contain stall positions.

Output

Print the largest possible minimum distance.

Subtasks

• 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$.

Examples

Input

5 3
1
2
8
4
9

Output

3

Explanation

Placing cows at $1,4,8$ achieves minimum distance $3$, and distance $4$ is impossible.