영어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)
Problem
Arash is back home again after the onsite-finals in Linköping and is starting to get back into everyday life. Now he just returned from a laundry room visit, and once again need to match his socks. He has N socks in total, but feel like he only really need K pairs. That means it is okay if N-2K socks remain unmatched.
Every one of his socks has a color F_i. Two socks i and j can be matched into a pair if the difference in color is strictly less than the integer D, that is |F_i - F_j| ≤ D. You want to help Arash find the smallest integer D such that he can match at least K pairs of socks!
Input
The input consists of two lines. The first line contains the two integers N and K (2 ≤ N ≤ 50000, 2 ≤ 2K ≤ N).
The second line contains N integers: F_1, F_2, …, F_N. The integers F_i will be in the range from 1 to 10^15 (inclusive).
Output
You should print one integer: The minimal difference D such that Arash can match at least K pairs of socks.
Scoring
Your solution will be tested on several groups of test cases. To get points for a group you need to pass all the tests of that group.
| Group | Points | Constraints |
| 1 | 40 | N ≤ 200, F_i ≤ 5000 for all i |
| 2 | 30 | N ≤ 1000 |
| 3 | 30 | No additional constraints |
예제
예제 1
5 2 3 8 1 5 9
3
예제 2
4 1 100 101 102 103
2
예제 3
10 4 81 92 42 45 62 5 4 85 73 22
9
예제 4
2 1 1000000000000 5000000000000
4000000000001