1626 : 차이(RAZLIKA)
- 제한시간
- 5000 ms
- 메모리제한
- 64 MB
- 해결횟수
- 21 회
- 시도횟수
- 104 회
문제
N개의 정수가 주어져 있다. 이 중에서 K개의 수를 지운 후 남은 N-K개의 수 중 임의로 뽑은 두 수의 차이의 최댓값 M과 최솟값 m의 합을 최소화하는 프로그램을 작성하여라.
입력형식
첫 번째 줄에는 N, K가 주어진다. (3 ≤ N ≤ 1,000,000, 1 ≤ K ≤ N-2)
두 번째 줄에는 N개의 정수가 주어진다. 각 정수의 절댓값은 5,000,000 이하이다.
출력형식
첫 번째 줄에 M+m의 최솟값을 출력한다.
입력 예5 2 -3 -2 3 8 6 |
출력 예7 |
Hint!
입력 예 2
6 2
-5 8 10 1 13 -1
출력 예 2
13
입력 예 3
6 3
10 2 8 17 2 17
출력 예 3
6