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

问题陈述

高桥为斯努克准备了N道菜。 这些菜从1到N编号，第i道菜的甜度为A_i，咸度为B_i。

高桥可以按他喜欢的任何顺序排列这些菜。 斯努克将按照他们排列的顺序吃这些菜，但如果在任何时候他吃过的菜的总甜度超过了X或总咸度超过了Y，他就不会再吃任何菜了。

高桥希望斯努克能吃尽可能多的菜。 如果高桥最优地排列这些菜，找出斯努克将吃掉的最大菜肴数量。

约束条件

• $1 \leq N \leq 80$
• $1 \leq A_i, B_i \leq 10000$
• $1 \leq X, Y \leq 10000$
• 所有输入值都是整数。

输入

输入从标准输入以下格式给出：

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

输出

以整数形式打印答案。

示例输入1

4 8 4
1 5
3 2
4 1
5 3

示例输出1

3

考虑高桥按照2, 3, 1, 4的顺序排列菜肴的场景。

• 首先，斯努克吃掉菜肴2。到目前为止的总甜度是3，总咸度是2。
• 接下来，斯努克吃掉菜肴3。到目前为止的总甜度是7，总咸度是3。
• 接下来，斯努克吃掉菜肴1。到目前为止的总甜度是8，总咸度是8。
• 总咸度已经超过了Y=4，所以斯努克将不再吃任何进一步的菜肴。

因此，在这种排列中，斯努克将吃掉三道菜。

无论高桥如何排列菜肴，斯努克都不会吃掉所有四道菜，所以答案是3。

示例输入2

2 1 1
3 2
3 2

示例输出2

1

示例输入3

2 100 100
3 2
3 2

示例输出3

2

示例输入4

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

示例输出4

3