最多吃掉的菜

题目描述

高桥君为 Snuke 君准备了 $N$ 道菜。

菜编号为 $1$ 到 $N$,菜 $i$ 的甜度为 $A_i$,咸度为 $B_i$。

高桥君可以按任意顺序排列这些菜。

Snuke 君会按排列的顺序吃菜,但如果某一时刻已吃掉的菜的甜度总和超过 $X$,或咸度总和超过 $Y$,他就不再吃后面的菜。

高桥君希望 Snuke 君尽可能多吃一些菜。

求高桥君最优排列时,Snuke 君能吃到的菜的最大数量。

输入格式

输入按以下格式从标准输入给出。

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

输出格式

以整数形式输出答案。

样例

4 8 4
1 5
3 2
4 1
5 3

3

考虑高桥君按 $2, 3, 1, 4$ 的顺序排列菜的情况。

首先,Snuke 君吃菜 $2$。到目前为止的甜度总和为 $3$,咸度总和为 $2$。

接着,Snuke 君吃菜 $3$。到目前为止的甜度总和为 $7$,咸度总和为 $3$。

接着,Snuke 君吃菜 $1$。到目前为止的甜度总和为 $8$,咸度总和为 $8$。

咸度总和超过了 $Y=4$,所以 Snuke 君不再吃后面的菜。

因此,在这种排列下,Snuke 君会吃掉三道菜。

无论高桥君如何排列,Snuke 君都不可能吃掉全部四道菜,所以答案是 $3$。

2 1 1
3 2
3 2

1

2 100 100
3 2
3 2

2

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

3

数据范围

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