Escape from Hell

Time limit2sMemory limit512 MB

Summary

Choose an order to use N energy drinks so the climber reaches length L on the earliest day without sinners catching up at night.

Level: Hard8 of 10
Topics: Greedy, Sorting, Implementation, Binary search
Solved: No attempts yet

Problem

One day, Buddha looked down into hell and noticed an office worker. The man had done evil, such as forcing unreasonable workloads on his subordinates, but he had done exactly one good deed in his life: he refused an unfair demand from a customer in order to protect his subordinates' lives. Buddha decided that this deed earned him a chance to escape, and lowered a single strand of spider silk into hell.

The office worker started to climb the silk, but the way out is $L$ meters long, far too long for one day. He has $N$ energy drinks and drinks one of them each day. On the day he drinks the $i$ -th drink, he climbs $A_i$ meters during the daytime and then slides down $B_i$ meters during the night. If his height reaches $L$ meters or more during the daytime, he escapes at once without sliding down. After $N$ days the silk is cut.

He then noticed that other sinners climb the silk every night. During the $i$ -th night the sinners climb $C_i$ meters, and they never slide down during the day. If the sinners catch up with the office worker, a fight breaks out and the silk is cut. That is, if the sinners' height is greater than or equal to the office worker's height at the end of any night, he can no longer escape. The office worker and the sinners all start at height 0.

Write a program that chooses the best order in which to drink the energy drinks and prints the earliest day on which the office worker can escape. If he cannot escape, print -1.

Input

The input consists of a single test case.

N L
A1 B1
...
AN BN
C1
...
CN

The first line contains two integers $N$ ( $1 \le N \le 10^5$ ) and $L$ ( $1 \le L \le 10^9$ ), the number of energy drinks and the length of the spider silk. Among the next $N$ lines, the $i$ -th line contains two integers $A_i$ ( $1 \le A_i \le 10^9$ ) and $B_i$ ( $1 \le B_i \le 10^9$ ) describing the $i$ -th energy drink: on the day he drinks it, the office worker climbs $A_i$ meters in the daytime and slides down $B_i$ meters at night. Among the following $N$ lines, the $i$ -th line contains an integer $C_i$ ( $1 \le C_i \le 10^9$ ), the distance the other sinners climb during the $i$ -th night.

Output

Print the earliest day on which the office worker can escape. If he cannot escape, print -1.

Examples4

Example 1
Input
```
3 9
6 3
5 2
3 1
2
2
2
```
Expected output
```
2
```
Example 2
Input
```
5 20
3 2
4 2
6 3
8 4
10 5
4
2
3
4
5
```
Expected output
```
-1
```

Example 3

Input

Expected output

Example 4
Input
```
4 12
8 4
6 4
2 1
2 1
1
1
4
4
```
Expected output
```
-1
```