103644: [Atcoder]ABC364 E - Maximum Glutton

Problem Statement

Takahashi has prepared $N$ dishes for Snuke. The dishes are numbered from $1$ to $N$, and dish $i$ has a sweetness of $A_i$ and a saltiness of $B_i$.

Takahashi can arrange these dishes in any order he likes. Snuke will eat the dishes in the order they are arranged, but if at any point the total sweetness of the dishes he has eaten so far exceeds $X$ or the total saltiness exceeds $Y$, he will not eat any further dishes.

Takahashi wants Snuke to eat as many dishes as possible. Find the maximum number of dishes Snuke will eat if Takahashi arranges the dishes optimally.

Constraints

• $1 \leq N \leq 80$
• $1 \leq A_i, B_i \leq 10000$
• $1 \leq X, Y \leq 10000$
• All input values are integers.

Input

The input is given from Standard Input in the following format:

$N$ $X$ $Y$
$A_1$ $B_1$
$A_2$ $B_2$
$\vdots$
$A_N$ $B_N$

Output

Print the answer as an integer.

Sample Input 1

4 8 4
1 5
3 2
4 1
5 3

Sample Output 1

3

Consider the scenario where Takahashi arranges the dishes in the order $2, 3, 1, 4$.

• First, Snuke eats dish $2$. The total sweetness so far is $3$, and the total saltiness is $2$.
• Next, Snuke eats dish $3$. The total sweetness so far is $7$, and the total saltiness is $3$.
• Next, Snuke eats dish $1$. The total sweetness so far is $8$, and the total saltiness is $8$.
• The total saltiness has exceeded $Y=4$, so Snuke will not eat any further dishes.

Thus, in this arrangement, Snuke will eat three dishes.

No matter how Takahashi arranges the dishes, Snuke will not eat all four dishes, so the answer is $3$.

Sample Input 2

2 1 1
3 2
3 2

Sample Output 2

1

Sample Input 3

2 100 100
3 2
3 2

Sample Output 3

2

Sample Input 4

6 364 463
230 381
154 200
328 407
339 94
193 10
115 309

Sample Output 4

3