Problem Description

In Iroha's town, there are \(M+1\\) stations and \(N\\) trains, numbered from \(1\\) to \(M+1\\) and from \(1\\) to \(N\\) respectively.

The current time is \(0\\). Iroha is currently at station \(1\\) and wants to go to station \(M+1\\).

Train \(i\\) departs from station \(1\\) at time \(A\_i\\) and arrives at station \(j+1\\ (1≦j≦M)\\) at time \(A\_i+B\_i\\times j\\).

Iroha can run between station \(k\\ (1≦k≦M)\\) and station \(k+1\\) in \(L\\) units of time.

Iroha can change her means of transportation at stations, which takes negligible time. She cannot change her means of transportation anywhere other than at stations.

Determine the earliest time Iroha can reach station \(M+1\\).

Input Format

The input is given in the following format:

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

Output Format

Output the answer in one line, followed by a newline.

Sample Input and Output

Sample Input #1

3 3 4
4 2
2 3
3 4

Sample Output #1

10

Sample Input #2

3 3 3
4 2
2 3
3 4

Sample Output #2

9

Sample Input #3

1 100 10
100 1

Sample Output #3

200

Sample Input #4

3 139128390 220019821
3162336416461334 196423673
2909210940940890 272140126
31923189201903829 68312342

Sample Output #4

30490445798837804

Notes/Hints

Constraints

• All inputs are integers.
• \(1≦N≦10^5\\)
• \(1≦M, L≦3\\times10^8\\)
• \(0≦A\_i≦10^{17}\\)
• \(1≦B\_i≦3\\times10^8\\)

Sample Explanation 1

By moving as follows, Iroha can reach station \(M+1\\ (=4)\\) at time \(10\\):
- Wait for train \(2\\) to depart (time \(0\\) - time \(2\\))
- Take train \(2\\) to station \(2\\) (time \(2\\) - time \(5\\))
- Wait for train \(1\\) (time \(5\\) - time \(6\\))
- Take train \(1\\) to station \(4\\) (time \(6\\) - time \(10\\))

Sample Explanation 2

By moving as follows, Iroha can reach station \(M+1\\ (=4)\\) at time \(9\\):
- Run to station \(4\\) (time \(0\\) - time \(9\\))

Sample Explanation 3

By moving as follows, Iroha can reach station \(M+1\\ (=101)\\) at time \(200\\):
- Run to station \(2\\) (time \(0\\) - time \(10\\))
- Run to station \(1\\) (time \(10\\) - time \(20\\))
- Run to station \(4\\) (time \(20\\) - time \(50\\))
- Stay at station \(4\\) for \(20\\) units of time (time \(50\\) - time \(70\\))
- Run to station \(1\\) (time \(70\\) - time \(100\\))
- Take train \(1\\) to station \(101\\) (time \(100\\) - time \(200\\))

见题面 Input 部分

见题面 Output 部分