/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 400 点
問題文
数直線上に N 棟の家があり、1 から N までの番号が付けられています。 家 i は座標 X_i に位置しています。同じ座標に複数の家が位置していることもあります。
あなたは M 個の基地局を数直線上の任意の実数座標に配置します。そして、それぞれの基地局に対して非負整数の値の電波強度を設定します。
ある基地局の電波強度を x にしたとき、その基地局からの電波が家に届く条件は、その基地局とその家の距離が \displaystyle\frac{x}{2} 以下であることです。 特に x=0 の場合、その基地局と同じ座標に位置する家にのみ電波が届きます。
どの家にも少なくとも 1 つの基地局から電波が届くように基地局の位置と電波強度を設定するとき、電波強度の総和がとりうる最小値を求めてください。
なお、制約を満たす任意の入力に対して答えが整数であることが証明できます。
制約
- 1 \leq M \leq N \leq 5 \times 10^5
- 1 \leq X_i \leq 10^{12} (1 \leq i \leq N)
- 入力される数値は全て整数である。
入力
入力は以下の形式で標準入力から与えられる。
N M X_1 \dots X_N
出力
答えを整数として 1 行で出力せよ。
入力例 1
7 3 5 10 15 20 8 14 15
出力例 1
6
以下のように 3 つの基地局を置くことで、すべての家に電波が届きます。
- 座標 7.5 に電波強度 5 の基地局を置く。この基地局から電波が届くのは家 1,2,5 である。
- 座標 14.5 に電波強度 1 の基地局を置く。この基地局から電波が届くのは家 3,6,7 である。
- 座標 20 に電波強度 0 の基地局を置く。この基地局から電波が届くのは家 4 である。
このときの電波強度の総和は 6 です。
電波強度の総和が 6 より小さい配置で条件を達成することはできないので、6 を出力します。
入力例 2
7 7 5 10 15 20 8 14 15
出力例 2
0
入力例 3
7 1 5 10 15 20 8 14 15
出力例 3
15
Score : 400 points
Problem Statement
There are N houses numbered from 1 to N on a number line. House i is located at coordinate X_i. Multiple houses may be located at the same coordinate.
You place M base stations at arbitrary real coordinates on the number line. Then, you set a non-negative integer signal strength for each base station.
When the signal strength of a base station is set to x, The signal from that base station reaches a house if and only if the distance between the base station and the house is at most \displaystyle\frac{x}{2}. Particularly, when x=0, the signal reaches only houses located at the same coordinate as the base station.
Find the minimum possible sum of signal strengths when the positions and signal strengths of the base stations are set such that at least one base station's signal reaches every house.
It can be proved that the answer is an integer for any input satisfying the constraints.
Constraints
- 1 \leq M \leq N \leq 5 \times 10^5
- 1 \leq X_i \leq 10^{12} (1 \leq i \leq N)
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N M X_1 \dots X_N
Output
Output the answer as an integer in one line.
Sample Input 1
7 3 5 10 15 20 8 14 15
Sample Output 1
6
By placing three base stations as follows, signals reach all houses.
- Place a base station with signal strength 5 at coordinate 7.5. This base station reaches houses 1,2,5.
- Place a base station with signal strength 1 at coordinate 14.5. This base station reaches houses 3,6,7.
- Place a base station with signal strength 0 at coordinate 20. This base station reaches house 4.
The sum of signal strengths in this case is 6.
It is impossible to satisfy the condition with an arrangement where the sum of signal strengths is smaller than 6, so output 6.
Sample Input 2
7 7 5 10 15 20 8 14 15
Sample Output 2
0
Sample Input 3
7 1 5 10 15 20 8 14 15
Sample Output 3
15