分数: 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