Maximum Glutton

题目描述

Takahashi 为 Snuke 准备了 $N$ 道菜。 这些菜从 $1$ 到 $N$ 编号，第 $i$ 道菜的 甜度 为 $A_i$，咸度 为 $B_i$。 Takahashi 可以任意排列这些菜的顺序。 Snuke 会按照排列的顺序吃菜，但如果在某一时刻他已吃过的菜的总甜度超过 $X$ 或总咸度超过 $Y$，他将不会再吃任何菜。 Takahashi 希望 Snuke 吃尽可能多的菜。 如果 Takahashi 最优地排列这些菜，求 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 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 \leq N \leq 80$ $1 \leq A_i, B_i \leq 10000$ $1 \leq X, Y \leq 10000$ 所有输入值均为整数。考虑 Takahashi 将菜按顺序排列为 $2, 3, 1, 4$ 的情况。

首先，Snuke 吃第 $2$ 道菜。此时的总甜度为 $3$，总咸度为 $2$。 接着，Snuke 吃第 $3$ 道菜。此时的总甜度为 $7$，总咸度为 $3$。 接着，Snuke 吃第 $1$ 道菜。此时的总甜度为 $8$，总咸度为 $8$。 总咸度已超过 $Y=4$，因此 Snuke 不会再吃后面的菜。

因此，在这种排列下，Snuke 会吃三道菜。 无论 Takahashi 如何排列这四道菜，Snuke 都不会吃完全部四道菜，所以答案为 $3$.

标签: AtCoder|abc364E

来源

AtCoder|abc364E