Points:
300 (p)
Time limit:
1.0s
Memory limit:
256M
Input:
stdin
Output:
stdout
Lương Xiao Lin có \(n\) em gái có mức độ yêu thương lần lượt là \(a_1, a_2, ..., a_n\). Lương muốn chọn ra \(k\) cặp em gái rời nhau. Gọi \(x\) là chênh lệch lớn nhất giữa hai bạn trong một nhóm. Vì nếu chênh lệch mức độ yêu thương giữa 2 em gái quá lớn thì có thể một em sẽ buồn. Lương là anh trai cao cả, Lương không muốn em gái nào phải buồn. Do đó, Lương muốn x càng nhỏ càng tốt. Các bạn hãy tìm \(x\) giúp Lương nhé, Lương sẽ chia có các bạn 1 em gái nếu các bạn giúp Lương.
Input
-
Dòng đầu có 2 số nguyên \(n, k\).
-
Dòng thứ hai có \(n\) số nguyên \(a_1, a_2, \ldots, a_n\)
Output
- In ra một số nguyên là kết quả bài toán
Scoring
- Subtask \(1\) (\(100\%\) số điểm): \(2 \leq n \leq 3 \times 10^5, 1 \leq k \leq \dfrac{n}{2}\) và \(1 \leq a_i \leq 10^9\).
Example
Test 1
Input
6 3
1 4 3 7 11 9
Output
3
Note
chúng ta chia cặp như sau: \((1, 3), (4, 7), (9, 11)\). Cặp có khoảng cách lớn nhất là \((4, 7)\) và \(7-4=3\).
Test 2
Input
6 2
1 4 3 7 11 9
Output
2
Note
chia cặp \((3, 4), (7, 9)\).
Test 3
Input
6 1
1 4 3 7 11 9
Output
1
Note
chia cặp \((3, 4)\).
Comments
:v