Khoảng Phủ

Cho $n$ số nguyên $a_1, a_2, ..., a_n$ và một số nguyên $k$. Ta cần chọn ra $k$ giá trị đại diện là các số nguyên tùy ý $b_1, b_2, ..., b_k$.

Mỗi số nguyên $a_i$ ($1 ≤ i ≤ n$) sẽ được gán cho một trong các giá trị đại diện $b_j$ ($1 ≤ j ≤ k$). Độ lệch của việc gán này được tính bằng khoảng cách $|a_i - b_j|$.

Hãy tìm giá trị $D$ nhỏ nhất sao cho tồn tại cách chọn $k$ giá trị đại diện và cách gán tương ứng để khoảng cách giữa mỗi $a_i$ và giá trị đại diện của nó đều không vượt quá $D$. Nói cách khác, $D = \max_{1 ≤ i ≤ n} |a_i - b_{j(i)}|$ đạt giá trị nhỏ nhất.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên $n$ và $k$ ($1 ≤ k ≤ n ≤ 2 · 10^5$).

Dòng thứ hai chứa $n$ số nguyên $a_1, a_2, ..., a_n$ ($0 ≤ a_i ≤ 10^9$) với mọi chỉ số $i$ ($1 ≤ i ≤ n$).

Kết quả

In ra một số nguyên duy nhất là giá trị $D$ nhỏ nhất tìm được.

Chấm điểm

Subtask 1 (20 points). $k ≤ 2$

Subtask 2 (30 points). $n ≤ 16$

Subtask 3 (50 points). $1 ≤ k ≤ n ≤ 2 · 10^5$

Ví dụ

Input

5 2
1 3 7 9 11

Output

2

Ghi chú

Các subtask của bài toán:

• Subtask 1 ($20%$ số điểm): $k ≤ 2$.
• Subtask 2 ($30%$ số điểm): $n ≤ 16$.
• Subtask 3 ($50%$ số điểm): Không có ràng buộc gì thêm.

Với ví dụ trên, ta có thể chọn 2 giá trị đại diện là 2 và 9:

• Các số 1, 3 được gán cho giá trị đại diện 2 với độ lệch lớn nhất là $\max(|1-2|, |3-2|) = 1$.
• Các số 7, 9, 11 được gán cho giá trị đại diện 9 với độ lệch lớn nhất là $\max(|7-9|, |9-9|, |11-9|) = 2$.

Độ lệch lớn nhất tổng cộng là 2, đây là giá trị $D$ nhỏ nhất có thể đạt được.