Gas Stations

Michelle and Marie are taking a road trip in their car. They will drive along a long straight road with $n$ gas stations, numbered from 1 to $n$ in order along the road. At the start of the road, the car is in the city, and gas station 1 is at the same spot.

Gas station $i$ is $x_i$ kilometers from the beginning of the road and sells gas for $p_i$ dollars per liter. Gas can only be bought in whole liters. One liter of gas is enough to drive 1 unit of distance. The gas tank has a capacity of $C$ liters, and the tank starts empty.

Michelle and Marie have $B$ dollars to spend on gas. They do not plan to come back. How far along the road can they drive?

The first line contains three integers $n$, $B$, and $C$, the number of gas stations, the total budget in dollars, and the tank capacity in liters ($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 position of the $i$-th gas station and its gas price ($0 = x_1 < x_2 < \ldots < x_n \le 10^9$; $1 \le p_i \le 10^9$).

Print one integer, the maximum distance that can be driven along the road.

In the sample test, they can buy 1 liter of gas at the first station and drive 1 unit. Then they buy 5 liters at the second station and drive 3 more units to reach the third station. At that point the tank holds 2 liters. They buy 1 more liter and drive 3 more units, ending the trip at distance 7.