13031303 SUSTech Online Judge
Problem 1303 --Trip

1303: Trip

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 37  Solved: 12
[Submit][Status][Web Board]

Description

Pisces is going on a long trip. Initially, he takes \(P\) units of food with him, and the total length of the trip is \(L\) meters. To make himself energetic, Pisces consumes \(1\) unit of food when he goes through \(1\) meter. Besides, there are \(N\) villages along the trip, and in the \(i\)th of them Pisces could supplement \(a_i\) unit of food. Now, Pisces would like to find out what is the minimum number of times that he needs to supplement to reach the destination.

Input

The first line contains a single integer \(N(1\leq N\leq 10^4)\), which is the number of villages.

Each of the following \(N\) lines contains \(2\) integers, where integers in the \(i\)th line represents the distance from the \(i\)th village to the destination and the amount of food that Pisces can get in this village.

The last line contains \(2\) integers \(L(1\leq L\leq 10^6)\) and \(P(1\leq P\leq 10^6)\).

Output

Print the minimum number of times in order to reach the destination. If Pisces cannot reach the destination anyway, print "-1" (without quotes).

Sample Input

4
4 4
5 2
11 5
15 10
25 10

Sample Output

2

HINT

Source

 

[Submit][Status]