시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 44 17 16 44.444%

문제

수열이 주어졌을 때, M을 수열의 모든 두 원소의 차이 중 가장 큰 값이라고 한다. m은 그 차이 중 가장 작은 값이라고 한다.

크기가 N인 수열 V가 주어진다. 여기서 K개 수를 적절히 제거해서 M+m을 가능한 작게 만드는 프로그램을 작성하시오.

입력

첫째 줄에 N(3 ≤ N ≤ 1,000,000)과 K(1 ≤ K ≤ N-2)가 주어진다.

둘째 줄에 V의 원소가 공백으로 구분되어 주어진다. (-5,000,000 ≤ Vi ≤ 5,000,000)

출력

첫째 줄에 가장 작은 M+m을 출력한다.

예제 입력

5 2
-3 -2 3 8 6

예제 출력

7

힌트