차이(RAZLIKA) 5초 64MB

문제

N개의 정수가 주어져 있다. 이 중에서 K개의 수를 지운 후 남은 N-K개의 수 중 임의로 뽑은 두 수의 차이의 최댓값 M과 최솟값 m의 합을 최소화하는 프로그램을 작성하여라.

첫 번째 줄에는 N, K가 주어진다. (3 ≤ N ≤ 1,000,000, 1 ≤ K ≤ N-2) 두 번째 줄에는 N개의 정수가 주어진다. 각 정수의 절댓값은 5,000,000 이하이다.

첫 번째 줄에 M+m의 최솟값을 출력한다.

입력

5space_bar2
keyboard_return
-3space_bar-2space_bar3space_bar8space_bar6

출력

힌트

COCI 2012/2013 - 번역 : functionx
2013.02.23 모의테스트3