405750: GYM102058 M Coke Challenge

Mr. Jeong really loves coke. He loves so much that he drinks coke everyday without exception. One day, he decided to open a coke contest in Daejeon. To the winner, a box of cokes will be given!

N people participate in the contest. Each participant is given K mL of coke, and the one who finishes his/her coke earliest wins the contest. But it is painful to drink the whole coke in one time, so each person repeats drinking and taking a rest. More specifically, as soon as the contest starts, the ith participant starts to drink for t_i seconds, then takes a rest for s_i seconds, and repeats this process until no more coke remains. Moreover, everyone drinks A mL per second. The contest is over if one of the participants finished his/her coke.

Given the infomation of N participants, determine after how many seconds the contest is finished, since the contest begins.

The input starts with the first line containing three integers N (2 ≤ N ≤ 1000), K (1 ≤ K ≤ 10000), and A (1 ≤ A ≤ 100). The ith of the next N lines contains two integers t_i (1 ≤ t_i ≤ 100) and s_i (1 ≤ s_i ≤ 100), the information of ith participant. K is a multiple of A.

Write a single integer, the answer to the question.

2 100 1
10 5
5 10

145

4 100 2
30 30
49 2
50 50
20 10

50