Under construction

Still being built. Things may change

Refueling

Interview

Time limit2sMemory limit128 MB

Summary
Find the minimum number of gas station stops a truck must make, given starting fuel and station positions with fuel amounts, to reach a village on a line.
Level

Medium6 of 10

Topics
Greedy, Heap, Sorting
Solved
No attempts yet

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.

Examples1

  1. Example 1

    Input
    4
    4 4
    5 2
    11 5
    15 10
    25 10
    Expected output
    3