405750: GYM102058 M Coke Challenge

Memory Limit:512 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

M. Coke Challengetime limit per test1 secondmemory limit per test512 megabytesinputstandard inputoutputstandard output

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.

Input

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.

Output

Write a single integer, the answer to the question.

ExamplesInput
2 100 1
10 5
5 10
Output
145
Input
4 100 2
30 30
49 2
50 50
20 10
Output
50

加入题单

上一题 下一题 算法标签: