ストーリー

闇をつんざくような叫び声。僕もいろはちゃんもすぐに外の様子に気がついた。遠くの街のほうが赤く光って、異音を轟かせながら揺れる。「あれって…！」僕が"それ"に気がついたときには、いろはちゃんはもう走り出していた。

問題文

いろはちゃんのいる町には \(M+1\) 個の駅と \(N\) 個の電車があり、それぞれ \(1\) から \(M+1\)、\(1\) から \(N\) の番号が付けられている。

現在の時刻は \(0\) である。今いろはちゃんは駅 \(1\) におり、駅 \(M+1\) に行こうとしている。

電車 \(i\) は時刻 \(A_i\) に駅 \(1\) を出発し、駅 \(j+1\ (1≦j≦M)\) には時刻 \(A_i+B_i\times j\) に着く。

また、いろはちゃんは走ることで駅 \(k\ (1≦k≦M)\) と駅 \(k+1\) の間を \(L\) 単位時間かけて移動できる。

いろはちゃんは駅で移動手段を変えることができ、これにかかる時間は無視できる。駅以外の場所で移動手段を変えることはできない。

いろはちゃんが駅 \(M+1\) に着く最速の時刻を求めよ。

制約

• 入力はすべて整数
• \(1≦N≦10^5\)
• \(1≦M, L≦3\times10^8\)
• \(0≦A_i≦10^{17}\)
• \(1≦B_i≦3\times10^8\)

---

入力

入力は以下の形式で与えられる。

\\(N\\) \\(M\\) \\(L\\)
\\(A_1\\) \\(B_1\\)
\\(A_2\\) \\(B_2\\)
:
\\(A_N\\) \\(B_N\\)```

### 出力

答えを \\(1\\) 行に出力し、最後に改行せよ。

* * *

### 入力例 1

```plain

3 3 4
4 2
2 3
3 4

出力例 1

10

次のように移動すると、駅 \(M+1\ (=4)\) に時刻 \(10\) に着くことができる。

• 電車 \(2\) の出発を待つ ( 時刻 \(0\) - 時刻 \(2\) )
• 電車 \(2\) に乗って駅 \(2\) まで行く ( 時刻 \(2\) - 時刻 \(5\) )
• 電車 \(1\) を待つ ( 時刻 \(5\) - 時刻 \(6\) )
• 電車 \(1\) に乗って駅 \(4\) まで行く ( 時刻 \(6\) - 時刻 \(10\) )

---

入力例 2

3 3 3
4 2
2 3
3 4

出力例 2

9

次のように移動すると、駅 \(M+1\ (=4)\) に時刻 \(9\) に着くことができる。

• 駅 \(4\) まで走る ( 時刻 \(0\) - 時刻 \(9\) )

---

入力例 3

1 100 10
100 1

出力例 3

200

次のように移動すると、駅 \(M+1\ (=101)\) に時刻 \(200\) に着くことができる。

• 駅 \(2\) まで走る ( 時刻 \(0\) - 時刻 \(10\) )
• 駅 \(1\) まで走る ( 時刻 \(10\) - 時刻 \(20\) )
• 駅 \(4\) まで走る ( 時刻 \(20\) - 時刻 \(50\) )
• 駅 \(4\) で \(20\) 単位時間留まる ( 時刻 \(50\) - 時刻 \(70\) )
• 駅 \(1\) まで走る ( 時刻 \(70\) - 時刻 \(100\) )
• 電車 \(1\) に乗って駅 \(101\) まで行く ( 時刻 \(100\) - 時刻 \(200\) )

---

入力例 4

3 139128390 220019821
3162336416461334 196423673
2909210940940890 272140126
31923189201903829 68312342

出力例 4

30490445798837804

---

解説

解説