連續學習演算法讓 경근 有些疲憊，他覺得去另一個世界休息幾天會很不錯。有一天，상수 告訴了他一扇通往另一個世界的門所在的地方，於是他前往那裡。那裡確實有這樣一扇門，但門鎖著，並裝有一把能打開門的大型轉盤鎖。

鎖由上下排列的 $M$ 個轉盤組成。每個轉盤有 $R$ 個格子，可以向左或向右按整格轉動。每個格子可能有點，也可能沒有點。每個轉盤至少有一個點。據說，只要轉動轉盤，使某個位置垂直一列的所有格子都有點，門就會打開。各轉盤獨立轉動。由於轉盤很重、轉動費力，我們希望最小化所有轉盤轉動的格數之和。

上圖給出了一個例子。一種最佳方法是：從上往下，第一個轉盤向左轉一格，第二個向左轉兩格，第三個向右轉一格，第四個不動，共轉動 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 的檔案，其中必須實作以下函式。

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\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

下方給出了你的程式碼處理上述輸入時的執行範例。