ストーブ (Stove)

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

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

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

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

課題

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

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

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

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

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

• \(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 点]

• 追加の制限はない．

JOI 2018 · JCIOI · CC BY-SA 4.0