Problem : 229 - Backup

Problem Statistics

Solved Member: 12　　Submission: 42　　User Tried: 12

Statement:

你經營一家資訊科技公司它專為大型辦公室從事電腦資料備份服務。但是資料備份並不是一件容易的事，因此你設計了一個系統讓不同辦公室間能自動備份彼此間的資料，這樣你才有空閒回家打電動。

這些辦公室都坐落在同一條街道上。你決定把這些辦公室兩兩分成一對，並且在每一對辦公室所在的兩棟大樓之間鋪設網路電纜連接它們，使得它們可以備份彼此的資料。

然而，網路電纜是很昂貴的。當地的電信公司將只會提供給你k 條網路電纜，這意謂你只能安排k 對辦公室的備份（總共有2k 個辦公室）。每一個辦公室最多只能與另一個辦公室配對（也就是說，這些2k 個辦公室都必須是不同的）再者，電信公司是論公里收費。這意謂這k 對辦公室配對選擇必須使用越短的電纜越好。換句話說，所有配對辦公室的電纜長度加總後要越少越好。

舉例來說，假設你有5 個客戶的辦公室是坐落在同一條街，如下圖所示。這些辦公室分別坐落在離街道起點的1 公里、3 公里、4 公里、6 公里以及12 公里處。電信公司將只會供給你k=2 條電纜。

在這個問題中最好的配對方式是把第一個與第二個辦公室間連接在一起、第三個與第四個辦公室連接在一起。這樣就符合需求使用k=2 條電纜，其中第一條電纜的長度為3 公里-1 公里=2 公里、第二條電纜的長度為6 公里-4 公里=2 公里。這個配對方式總共需要4 公里的網路電纜，這也是電纜總長度需求最少的配對方式。

Input:Output:

輸入的第一個行將包括整數n 與k ，分別代表在這條街道上辦公室的個數(2 ≤ n≤ 100 000)與可供使用的網路電纜數(1 ≤ k ≤ ½ n)。

接下來的n 行中每一行將有一個整數(0 ≤ s ≤ 1 000 000 000)代表每一個辦公室離街道起點的距離。這些整數將會排序過且以從數值小到數值大的方式呈現。不會有兩個辦公室在同一個位置上。

輸出一個整數，即可連結k 對2k 個不同位置辦公室所需的最小網路電纜總長度。

Sample Input:Sample Output:

5 2
1
3
4
6
12

Source:

APIO 2007

Problem Setter

hanhan0912

Testdata:

Test	Time	Memory	Score
0	1000ms	32767kb
1	1000ms	32767kb	5
2	1000ms	32767kb	5
3	1000ms	32767kb	5
4	1000ms	32767kb	5
5	1000ms	32767kb	5
6	1000ms	32767kb	5
7	1000ms	32767kb	5
8	1000ms	32767kb	5
9	1000ms	32767kb	5
10	1000ms	32767kb	5
11	1000ms	32767kb	5
12	1000ms	32767kb	5
13	1000ms	32767kb	5
14	1000ms	32767kb	5
15	1000ms	32767kb	5
16	1000ms	32767kb	5
17	1000ms	32767kb	5
18	1000ms	32767kb	5
19	1000ms	32767kb	5
20	1000ms	32767kb	5