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 ti seconds, then takes a rest for si 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 ti (1 ≤ ti ≤ 100) and si (1 ≤ si ≤ 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
