Informatica Online Judge

  도망가는 소들 [1965 / 07AD]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 6   Total Tried : 6


The Champion of this Problem (C++) : gs16022 - 0ms / 1037byte
My Best Submission (C++) : N/A

[gs16044]

Background

농부 엉화는 $N$마리의 소들을 가지고 있다. 소들이 계속해서 도망가자 화가 난 엉화는 소들을 두 마리씩 짝지어서 묶어놓기로 결심했다. 엉화는 끈을 $C$개 가지고 있어서 총 $2C$ 마리의 소들을 묶을 수 있다. $2C$는 항상 $N$ 이하이다. 단 이 $2C$ 마리의 소들은 모두 달라야 한다.

즉, $1$번 소와 $2$번 소를 묶은 후에, $1$번 소와 $3$번 소를 묶을 수는 없다는 것이다. 엉화는 최소 비용으로 소를 묶고 싶어한다. 여기서 비용이란 소들을 묶는 끈의 길이의 총합이다.

소들은 $x$축 위에 일렬로 서 있다.

아래 예제를 보자.

$N = 7, C = 2$ 라고 하자. 총 $7$마리 소들의 $x$ 좌표가 아래와 같다고 하자.

$3$ $10$ $15$ $16$ $18$ $27$ $36$

첫 번째 방법은 $(15, 16)$ 의 소와 $(3, 10)$ 의 소를 묶는 것이다.
이 때의 비용은 $1 + 7 = 8$ 이다.

두 번째 방법은 $(10, 15)$의 소와 $(16, 18)$의 소를 묶는 것이다.
이 때의 비용은 $5 + 2 = 7$ 이다.

두 번째 방법이 최적의 방법이며, 이 때의 비용은 $7$이다.
이와 같이 $N$, $C$, 소들의 $x$좌표가 주어질 때, 엉화가 쓸 최소 비용을 구하자.

Input

첫 줄에 두 정수 $N$, $C$이 주어진다.

$N <= 100000, C <= N/2$ 이다.

두 번째 줄에 $N$개의 소들의 $x$좌표가 오름차순으로 주어진다. 어느 두 소도 같은 $x$좌표를 갖지 않는다.

$x$좌표는 $10$억 이하의 음이 아닌 정수다.

Output

엉화가 낼 최소 비용을 한 줄로 출력한다.

IO Example

입력 예제
7 2
3 10 15 16 18 27 36

출력 예제
7

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]