アルゴリズムの勉強を続けて少し疲れた 경근 は、別の世界で数日休めたらよいと思った。ある日、상수 から別の世界への扉の場所を聞き、そこへ向かった。扉はあったが鍵が掛かっており、開けるための大きなダイヤル式の錠が付いていた。

錠は縦に並んだ $M$ 個のダイヤルからなる。各ダイヤルは $R$ 個のマスを持ち、左右にマス単位で回せる。各マスには点がある場合とない場合があり、各ダイヤルには少なくとも 1 個の点がある。ダイヤルを回して、ある位置で縦一列のすべてのマスに点があるようにすると扉が開く。それぞれは独立に回る。非常に重く回すのが大変なので、回したマス数の合計を最小にしたい。

上図は一例である。最適な方法の 1 つは、上から 1 番目を左へ 1 マス、2 番目を左へ 2 マス、3 番目を右へ 1 マス回し、4 番目を回さず、合計 4 マス回すことである。

ダイヤルの大きさと点の位置を受け取り、最小の合計マス数で扉を開ける方法を求めるプログラムを作成せよ。点の位置はダイヤル番号とマス番号の組で与えられる。一番上は 0 番で、下へ行くと 1 ずつ増え、一番下は $M-1$ 番となる。マス番号は任意の共通の位置（縦一列）のマスを 0 番とし、右へ 1 ずつ増える。0 番の左は $R-1$ 番である。与えられる点の座標は重複しない。

long long findMinClicks( int M, int R, vector< pair<int, int> > P )

$M$ はダイヤル数、$R$ は各ダイヤルのマス数である。$P$ は $N$ 個の int の組からなる配列である。各組の最初の数はダイヤル番号、次はマス番号である。座標は重複しない。findMinClicks() は、扉を開けるために回す合計マス数の最小値を返さなければならない。

実装の詳細

dial.cpp という名前のファイルをちょうど 1 つ提出し、次の関数を実装せよ。

long long findMinClicks( int M, int R, vector< pair<int, int> > P )

この関数は上の説明どおりに動作しなければならない。内部で使うほかの関数を作ってもよい。提出コードは入出力やほかのファイルへのアクセスを行ってはならない。

採点プログラムの例

提供される採点プログラムは次の形式で入力を読む。

• 1 行目：整数 $N$, $M$, $R$。
• 2 行目から $N+1$ 行目：整数 $D_i$, $C_i$。

ここで $(D_i,C_i)$ は $i$ 番目の点の座標である。採点プログラムは findMinClicks() の返り値を 1 行に出力する。

制約

• $1\le R\le10^9$, $1\le N\le\min(MR,500\,000)$, $1\le M\le N$.

小課題

小課題 1 (10 点)

• $1\le N\le5\,000$, $1\le R\le5\,000$.

小課題 2 (15 点)

• $1\le M\le5\,000$, $1\le R\le5\,000$.

小課題 3 (16 点)

• $1\le N\le5\,000$.

小課題 4 (109 点)

追加の制約はない。

入出力例

入力 1

7 4 20
1 3
0 2
2 6
3 8
3 1
2 0
1 8

上の入力に対するコードの実行例を以下に示す。