루미 알고리즘

#1341플래티넘Sock Matching 2

PO 2014 훈련 캠프코딩출제 Oskar Werkelin Ahlin영어 원문이 문제가 어렵다면 — 배우는 순서 보기

영어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)

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.

GroupPointsConstraints
140N ≤ 200, F_i ≤ 5000 for all i
230N ≤ 1000
330No 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

출처 표기

출처: Programmeringsolympiaden 2014년 훈련 캠프 · 원문 페이지 · 이용 조건 CC BY-SA · LaTeX 원문을 화면용 글로 옮겼습니다(수식·표의 모양이 다를 수 있습니다). 내용은 고치지 않았습니다.

크리에이티브 커먼즈 저작자표시-동일조건변경허락.

문제 출처: 한국정보올림피아드(KOI) (CC BY-NC-SA 4.0) · International Olympiad in Informatics (IOI) (CC BY) · Centre for Education in Mathematics and Computing (CEMC), University of Waterloo (CC BY-NC 4.0) · Programmeringsolympiaden (CC BY-SA) · CSES Problem Set (Antti Laaksonen) (CC BY-NC-SA 4.0). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.