시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 82 21 14 22.581%

문제

오늘은 기쁜 날이다. 개미와 코끼리의 결혼식 날이기 때문이다. 결혼 축하 의식으로 기차놀이를 하기로 했다. 기차놀이란 뒷사람이 앞사람의 어깨에 손을 얹고 한 줄로 마을을 돌아다니는 것이다. 그런데 앞사람과 뒷사람의 키 차이가 많이 나면 기차가 아름다워 보이지 않는다. 아름다움을 중요시 여기는 “앙두레 강”은 기차가 아름답게 보이도록 기차에서 사람들의 순서를 잘 조정하기로 했다.

인접한 앞뒤사람의 키 차이를 모두 더한 것이 최소가 될 때 기차는 가장 아름답게 보인다.

하지만 한 가지 문제가 있다. 결혼식에 사자가족도 참석했는데 사자가족은 서열이 엄격해서 서열이 낮은 사자가 서열이 높은 사자보다 기차에서 앞쪽에 위치하면 안 된다. 이 조건만 만족한다면 결혼식에 참석한 사람들의 순서를 마음대로 바꾸어도 된다.

“앙두레 강”을 도와 결혼 축하 기차를 아름답게 만들어 보도록 하자.

입력

첫 줄에 N(N <= 10000)과 K(K <= N, K <= 1000)가 입력된다. N은 결혼식에 참가한 사람의 수이고 K는 결혼식에 참가한 사자가족의 수이다. 바로 이어서 (우선순위가 높은 사자부터) 사자가족의 키가 K줄에 걸쳐 입력된다. 그리고 그 다음 줄부터 (N-K)줄에 다른 사람들의 키가 입력된다. 모든 입력은 int 범위이다.

출력

기차에서 인접한 앞뒤사람의 키 차이를 모두 더한 값을 출력하시오. 답은 항상 int 범위이다.

예제 입력

5 3 
1900
1300
1500
1200
1600

예제 출력

1000

힌트

출처

  • 잘못된 조건을 찾은 사람: pichulia