cho.sh
Notes
Loading...

Refueling

Time limit

2s

Memory limit

128 MB

Problem

A driver is traveling through a jungle on a straight road. The truck's fuel tank has a leak, so it loses 1 liter of fuel for every 1 kilometer traveled. The truck must reach the nearest village to be repaired, but it may run out of fuel on the way.

Fortunately, there are N gas stations along the road. Stopping in the middle of the jungle is dangerous, so the driver wants to minimize the number of gas-station stops.

The truck's fuel tank has no capacity limit, so it can hold any amount of fuel. Given each gas station's position and the amount of fuel available there, find the minimum number of stops needed to reach the village.

The jungle, the truck, the gas stations, and the village all lie on the same straight line. Every gas station is to the right of the truck's starting position.

Input

The first line contains the number of gas stations N. (1 <= N <= 10,000)

Each of the next N lines contains two integers a and b describing one gas station. a is the distance from the starting position to that station, and b is the amount of fuel that can be obtained there. (1 <= a <= 1,000,000, 1 <= b <= 100)

The last line contains two integers L and P. L is the distance from the starting position to the village, and P is the amount of fuel initially in the truck. (1 <= L <= 1,000,000, 1 <= P <= 1,000,000)

All gas stations and the village are at distinct positions, and the village is to the right of every gas station.

Output

Print the minimum number of gas-station stops needed to reach the village. If the village cannot be reached, print -1.