ストーブ(Stove)

JOI 君の部屋にはストーブがある．JOI 君自身は寒さに強いのでひとりで部屋にいるときはストーブをつける必要はないが，来客があるときはストーブをつける必要がある．

この日，JOI 君のもとにはN 人の来客がある．i 番目(1 \leq i \leq N) の来客は時刻T_i に到着し，時刻T_i + 1に退出する．同時に複数人の来客があることはない．

JOI 君は任意の時刻にストーブをつけたり消したりできる．ただし，ストーブをつける度にマッチを1本消費する．JOI 君はマッチをK 本しか持っていないので，K 回までしかストーブをつけることができない．一日のはじめにストーブは消えている．

ストーブをつけているとその分だけ燃料を消費するので，ストーブをつけたり消したりする時刻をうまく定めて，ストーブがついている時間の合計を最小化したい．

課題

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

入力

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

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

出力

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

制限

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

• 1 \leq N \leq 100 000．
• 1 \leq K \leq N．
• 1 \leq T_i \leq 1 000 000 000 (1 \leq i \leq N)．
• T_i < T_{i+1} (1 \leq i \leq N - 1)．

問入出力例

入力例1

3 2
1
3
6

出力例1

4

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

• 1 番目の来客が到着する時刻1 にストーブをつける．
• 2 番目の来客が退出する時刻4 にストーブを消す．
• 3 番目の来客が到着する時刻6 にストーブをつける．
• 3 番目の来客が退出する時刻7 にストーブを消す．

ストーブをつけている時間の合計を4 未満にすることはできないので，答えとして4 を出力する．

入力例2

3 1
1
2
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

情報オリンピック日本委員会作 『第17 回日本情報オリンピック(JOI 2017/2018) 本選』