006 - ストーブ (Stove)

問題

　JOI 君の部屋にはストーブがある．JOI 君自身は寒さに強いのでひとりで部屋にいるときはストーブをつける必要はないが，来客があるときはストーブをつける必要がある．
この日， JOI 君のもとには N 人の来客がある． i 番目 ( 1 ≦ i ≦ N ) の来客は時刻 T_i に到着し，時刻 T_i + 1 に退出する．同時に複数人の来客があることはない．
　JOI 君は任意の時刻にストーブをつけたり消したりできる．ただし，ストーブをつける度にマッチを 1 本消費する． JOI 君はマッチを K 本しか持っていないので， K 回までしかストーブをつけることができない．一日のはじめにストーブは消えている．
　ストーブをつけているとその分だけ燃料を消費するので，ストーブをつけたり消したりする時刻をうまく定めて，ストーブがついている時間の合計を最小化したい．

課題

　JOI 君の部屋への来客の情報と， JOI 君の持っているマッチの本数が与えられたとき，ストーブがついている時間の合計の最小値を求めよ．

入力

　標準入力から以下の入力を読み込め．

• 1 行目には， 2 つの整数 N , K が空白を区切りとして書かれている．これは， JOI 君の部屋に N 人の来客があり，　JOI 君は K 本のマッチを持っていることを表す．
• 続く　N　行のうちの　i　行目　( 1　≦　i　≦　N )　には，整数　T_i　が書かれている．これは，　i　番目の来客が時刻　T_i　に到着し，時刻　T_i + 1　に退出することを表す．

出力

　標準出力に，ストーブがついている時間の合計の最小値を 1 行で出力せよ．

制約

　すべての入力データは以下の条件を満たす．

• 1 ≦ N ≦ 100 000
• 1 ≦ K ≦ N
• 1 ≦ T_i ≦ 1 000 000 000 ( 1 ≦ i ≦ N )
• T_i < T_{i + 1} ( 1 ≦ i ≦ N )

小課題

小課題 1 [20 点]

　以下の条件を満たす．

• N ≦ 20
• 1 ≦ T_i ≦ 20 ( 1 ≦ i ≦ N )

小課題 2 [30 点]

• N ≦ 5000 を満たす．

小課題 3 [50 点]

• 追加の制限はない．

入出力例

入力例 1

3 2
1
3
6

出力例 1

4

　この入力例では， JOI 君の部屋への来客が 3 人ある．以下のようにストーブをつけたり消したりすると， 来客がある間はストーブがついており，ストーブをつける回数は 2 回であり，ストーブがついている時間の合計は (4 - 1) + (7 - 6) = 4 である．

入力例 2

3 1
1
3
6

出力例 2

6

　この入力例では， JOI 君は 1 回しかストーブをつけることができないので， 1 番目の来客が到着する時刻 1 ストーブをつけ， 3 番目の来客が退出する時刻 7 にストーブを消せばよい．
来客が退出する時刻と，その次の来客が到着する時刻が一致する場合があることに注意せよ．

入力例 3

3 3
1
3
6

出力例 3

3

　この入力例では， JOI 君は来客が到着する度にストーブをつけ，来客が退出する度にストーブを消せばよい．

入力例 4

10 5
1
2
5
6
8
11
13
15
16
20

出力例 4

12