최대 부분집합

면접 대비

시간 제한1초메모리 제한512 MB

요약

N개의 정수 중 K개를 골라 선택한 값들 사이의 최소 간격을 최대로 만드는 값을 구한다. 같은 값을 두 번 고르면 간격은 0이 된다.

난이도: 보통10점 중 5점
유형: 이분 탐색, 그리디, 정렬, 배열
정답자: 아직 제출이 없습니다

문제

정수 중복집합의 값은 서로 다른 두 원소의 차의 최솟값으로 정의한다. 중복집합이 같은 값을 가진 두 원소를 포함하면 그 두 원소는 서로 다른 원소로 취급하므로 중복집합의 값은 0이다.

N개의 원소로 이루어진 정수 중복집합 A가 주어질 때, A의 부분집합 중 K개의 원소로 이루어진 것의 값 중 최댓값을 구하자.

입력

첫째 줄에 두 정수 N K (2 ≤ K ≤ N ≤ 100,000)가 주어진다. N은 A의 원소 개수이고 K는 찾고자 하는 A의 부분집합의 원소 개수이다. 둘째 줄에 N개의 정수 A1, A2, ..., AN (0 ≤ Ai ≤ 1,000,000,000)가 주어지며, 이는 집합 A의 원소를 나타낸다.

출력

A의 부분집합 중 K개의 원소로 이루어진 것의 값 중 최댓값을 한 줄에 출력한다.

예제3

예제 1
입력
```
4 2
1 2 4 10
```
예상 출력
```
9
```
예제 2
입력
```
4 3
1 2 4 10
```
예상 출력
```
3
```
예제 3
입력
```
4 4
1 2 4 10
```
예상 출력
```
1
```