22136_BrotherLiao'sGame

Zhangliao is a smart boy with long hair, and everybody calls him Brother Liao. Brother Liao likes playing a funny computer game. When the game begins, there are n blockhouses. Each blockhouse has a defensive value and a bonus value. The player has a initial attack value. He will get one score on destroying one blockhouse. Every time, Brother Liao chooses a blockhouse as a target to attack. As all the undestroyed blockhouses will work together to resist, to destroy the target blockhouse, the player's attack value must be larger than or equal to the sum of defensive value of all the undestroyed blockhouses, otherwise Brother Liao will lose the game. If the player succeeds to destroy the target blockhouse, his attack value will EQUAL to the bonus value of the target blockhouse, and then Brother Liao will choose the next target.

As Brother Liao is good at programming, he has modified the game. Before the game starts, he can eliminate any blockhouses as he likes using bombs, but he will not get scores through this way. How many scores can Brother Liao get at most?

There are several test cases in the input.

Each test case start with a line containing a positive integer N ( N ≤ 1000 ), which is the number of blockhouses;

N lines followed;

The i-th line contains two nonnegativc integers, which are the defensive value and bonus of the i-th blockhouse respectively. They would not exceed 2000000.

The last line contains an integer which is the player's initial attack value.

The input terminates with EOF.

For each test case, output the scores that Brother Liao can get at most.

3
10 9
25 30
8 7
50
5
100 230
334 331
33 288
35 100
334 22
600

3
4