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

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

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

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

課題

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

制限

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

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

小課題

小課題 1 [20 点]

以下の条件を満たす．

• N \leqq 20．
• 1 \leqq T_i \leqq 20 (1 \leqq i \leqq N)．

小課題 2 [30 点]

• N \leqq 5\,000 を満たす．

小課題 3 [50 点]

• 追加の制限はない．

入力例 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