시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 28 13 12 48.000%

문제

Let us define the value of a multiset of integers is the minimum difference between any two distinct elements. If a multiset contains two elements with the same value, then the two elements are considered different elements thus the value of the multiset is 0.

Given a multiset of integers A consisting of N elements, we want to find the value of the subset of A consisting of K elements which has the maximum value.

입력

The first line contains two integers: N K (2 ≤ KN ≤ 100,000) in a line denoting the number of elements of A and the number of elements of the subset of A we are looking for. The second line contains N integers: A1, A2, ..., AN (0 ≤ Ai ≤ 1,000,000,000) representing the elements of set A.

출력

The output contains the value of the subset of A consisting of K elements which has the maximum value, in a line.

예제 입력 1

4 2
1 2 4 10

예제 출력 1

9

On the first sample, the optimal subset is {1, 10}. The value is 10 - 1 = 9.

예제 입력 2

4 3
1 2 4 10

예제 출력 2

3

On the second sample, the optimal subset is {1, 4, 10}. The value is 4 - 1 = 3.

예제 입력 3

4 4
1 2 4 10

예제 출력 3

1

On the third sample, the optimal subset is {1, 2, 4, 10}. The value is 2 - 1 = 1.