Coke Drinking Contest

Time limit1sMemory limit512 MB

Summary

Given N entrants who each drink A mL per second with fixed drinking and resting periods, find when the first entrant finishes K mL.

Level: Easy3 of 10
Topics: Math, Simulation, Implementation
Solved: No attempts yet

Problem

Taeyeong likes coke so much that he cannot get through a single day without it, and the coke made by Jaemin's company is his favorite. Jaemin decided to sponsor him, and with that money Taeyeong is holding the first coke drinking contest in Daejeon.

$N$ people enter the contest. Each entrant receives $K$ mL of coke and starts drinking the moment the bell rings, and the first person to empty the cup wins. Drinking it all at once hurts because of the carbonation, so every entrant alternates between drinking and resting. Each entrant drinks $A$ mL per second, and entrant $i$ repeats a cycle of drinking for $t_i$ seconds and then resting for $s_i$ seconds. The winner is decided at the instant some entrant has 0 mL left, and the contest ends there.

Given the information of the $N$ entrants, print how many seconds after the start the winner is decided.

Input

The first line contains the natural numbers $N$ ( $2 \le N \le 1000$ ), $K$ ( $1 \le K \le 10000$ ), and $A$ ( $1 \le A \le 100$ ), separated by spaces. $K$ is a multiple of $A$ . Each of the next $N$ lines contains the natural numbers $t_i$ ( $1 \le t_i \le 100$ ) and $s_i$ ( $1 \le s_i \le 100$ ) for entrant $i$ .

Output

Print the time at which the winner is decided, as an integer number of seconds counted from the start of the contest.

Examples2

Example 1
Input
```
2 100 1
10 5
5 10
```
Expected output
```
145
```
Example 2
Input
```
4 100 2
30 30
49 2
50 50
20 10
```
Expected output
```
50
```