← 返回题目列表

AtCoder · abc364_e

H. 最大贪食

中文机器翻译题面 查看原题

分数: 475 点

问题陈述

高桥已经准备好了 N Snuke 的菜肴。 菜品的编号是从 1 to N和菜 i 有一个 甜蜜 of A_i 和 咸味 of B_i.

高桥可以按照他喜欢的任何顺序排列这些菜肴。 Snuke 会按照菜品的排列顺序吃菜,但如果在任何时候他吃过的菜品的总甜度超过了 X 或总咸味超过 Y,他不会再吃任何菜了。

高桥希望 Snuke 吃尽可能多的菜。 如果高桥以最佳方式排列菜肴,求 Snuke 吃的最多菜肴数量。

约束

  • 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.

  • 首先,Snuke吃菜 2。到目前为止的总甜度是 3,总咸味是 2.
  • 接下来,Snuke吃菜 3。到目前为止的总甜度是 7,总咸味是 3.
  • 接下来,Snuke吃菜 1。到目前为止的总甜度是 8,总咸味是 8.
  • 总咸度已超标 Y=4,这样 Snuke 就不会再吃任何菜肴了。

因此,在这个安排中,Snuke 将吃三道菜。

无论高桥如何安排菜肴,Snuke都不会吃完所有四道菜,所以答案是 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