27197번 - Gas Stations 다국어

문제

Michelle and Marie went to a journey by their car. During the journey they are going to drive along the long straight road. There are $n$ gas stations on the road. Gas stations are numbered from 1ドル$ to $n$ along the road. Initially the car is located in the city at the beginning of the road, at the same place there is a gas station number 1ドル$.

Gas station number $i$ is located at the distance of $x_i$ kilometers from the beginning of the road and sells gas for the price of $p_i$ dollars per liter. It is only allowed to purchase an integer number of liters of gas at each station. One liter of gas is enough to drive 1ドル$ unit of distance along the road. The gas tank of the car has the capacity of $C$ liters. Initially the tank is empty.

Michelle and Marie have $B$ dollars in total to be spent on gas. How far along the road are they able to go if they don't bother about the way back yet?

입력

The first line of input contains three integers $n,ドル $B$ and $C$ --- the number of gas stations, total budget in dollars and the capacity of the gas tank in liters correspondingly (1ドル \le n \le 10^5$; 1ドル \le B \le 10^9$; 1ドル \le C \le 10^9$).

Each of the next $n$ lines contains two integers $x_i$ and $p_i$ --- the coordinate of $i$-th gas station and the gas price there correspondingly (0ドル = x_1 < x_2 < \ldots < x_n \le 10^9$; 1ドル \le p_i \le 10^9$).

출력

Output one integer --- maximal possible distance that may be driven along the road.

제한

노트

In the sample test it is possible to buy 1ドル$ liter of gas at the first station, drive 1ドル$ unit of distance, buy 5ドル$ liters of gas at the second station, drive another 3ドル$ units of distance to get to the third station. At this moment there are 2ドル$ liters of gas in the tank, the friends can buy another 1ドル$ liter of gas and drive another 3ドル$ units of distance, finishing their trip at a distance of 7ドル$ from the beginning.