ストーリー

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

问题描述

在いろはちゃん所在的城镇有 \(M+1\) 个车站和 \(N\) 辆电车，它们分别被编号为 \(1\) 到 \(M+1\) 和 \(1\) 到 \(N\)。

当前时间为 \(0\)。现在いろはちゃん正站在车站 \(1\)，想要前往车站 \(M+1\)。

电车 \(i\) 在时间 \(A_i\) 离开车站 \(1\)，并在时间 \(A_i+B_i\times j\) 到达车站 \(j+1\ (1≦j≦M)\)。

此外，いろはちゃん可以通过奔跑在车站 \(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

```plain

3 3 4
4 2
2 3
3 4

输出样例 1

10

按照以下方式移动，可以在时刻 \(10\) 到达车站 \(M+1 (=4)\)。

• 等待电车 \(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

按照以下方式移动，可以在时刻 \(9\) 到达车站 \(M+1 (=4)\)。

• 奔跑至车站 \(4\) ( 时间 \(0\) - 时间 \(9\) )

---

输入样例 3

1 100 10
100 1

输出样例 3

200

按照以下方式移动，可以在时刻 \(200\) 到达车站 \(M+1 (=101)\)。

• 奔跑至车站 \(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

---

解答

解答