COCI 2012/2013 - 번역 : functionx <br>2013.02.23 모의테스트3- 차이(RAZLIKA) > 문제은행 : 정보올림피아드&알고리즘




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




경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP