Chia Cặp 2

View as PDF

Points: 200 (p) Time limit: 1.0s Memory limit: 256M Input: stdin Output: stdout

Cho \(n\) học sinh có năng lực \(a_1\), \(a_2\),..., \(a_n\). Thầy giáo muốn chọn ra \(k\) cặp học sinh rời nhau. Gọi \(x\) là chênh lệch nhỏ nhất giữa hai bạn trong một nhóm. Thầy muốn \(x\) càng lớn càng tốt. Hãy in ra \(\max x\).

Input

  • Dòng đầu có 2 số nguyên \(n, k \ (2 \leq n \leq 3 \times 10^5, 1 \leq k \leq \dfrac{n}{2})\).

  • Dòng thứ hai có \(n\) số nguyên \(a_1, a_2, ..., a_n \ (1 \leq a_i \leq 10^9)\)

Output

  • In ra một số nguyên là kết quả bài toán

Example

Test 1

Input
6 2
1 4 3 7 12 9
Output
8
Note

chúng ta chia cặp như sau: \((1, 9), (3, 12)\). Cặp có khoảng cách nhỏ nhất là \((1, 9)\)\(9-1=8\).

Test 2

Input
6 1
1 4 3 7 11 9 
Output
10
Note

chia cặp \((1, 11)\).


Comments

There are no comments at the moment.