Problem Description

A group of dwarfs have fallen into a deep pit and, being too short to climb out, they decide to build a human ladder. Specifically, one dwarf stands on another's shoulders until the topmost dwarf can reach the edge of the pit with his outstretched arms.

For each dwarf, we know the height from his feet to his shoulders, denoted as \( A_i \), and the length of his arms, denoted as \( B_i \). The depth of the pit is \( H \).

If we use dwarfs \( 1, 2, 3, \ldots, k \) to form a ladder such that \( A_1 + A_2 + A_3 + \ldots + A_k + B_k \geq H \), then dwarf \( k \) can escape the pit. Once a dwarf escapes, he cannot be used to form the ladder again.

We want to maximize the number of dwarfs that can escape. Determine the maximum number of dwarfs that can escape.

Input Format

The first line contains an integer \( N \), representing the number of dwarfs. The next \( N \) lines each contain two integers \( A_i \) and \( B_i \). The last line contains \( H \).

Output Format

Output a single integer representing the maximum number of dwarfs that can escape.

Sample Input and Output

Sample Input #1

2
20 10
5 5
30

Sample Output #1

2

Sample Input #2

2
20 10
5 5
35

Sample Output #2

1

Notes/Hints

For \( 30\% \) of the test cases, \( N \leq 200 \).

For \( 100\% \) of the test cases, \( 1 \leq N \leq 2000 \), \( 1 \leq A_i, B_i, H \leq 10^5 \).

见题面 Input 部分

见题面 Output 部分