Minimum Glutton

题目描述

有 $N$ 道菜，第 $i$ 道菜的 甜度 为 $A_i$，咸度 为 $B_i$。 Takahashi 计划以任意他喜欢的顺序排列这 $N$ 道菜并按该顺序食用。 他会按排列的顺序吃菜，但一旦他已吃菜的总甜度超过 $X$ 或总咸度超过 $Y$，就会停止吃。 求他最终可能吃到的最小菜数。

输入格式

输入由标准输入按以下格式给出： $N$ $X$ $Y$ $A_1$ $A_2$ $\ldots$ $A_N$ $B_1$ $B_2$ $\ldots$ $B_N$

输出格式

输出答案。

4 7 18
2 3 5 1
8 8 1 4

2

5 200000000000000 200000000000000
1 1 1 1 1
2 2 2 2 2

5

8 30 30
1 2 3 4 5 6 7 8
8 7 6 5 4 3 2 1

6

提示

$1 \leq N \leq 2 \times 10^5$ $1 \leq X, Y \leq 2 \times 10^{14}$ $1 \leq A_i, B_i \leq 10^9$ 所有输入值均为整数。第 $i$ 道菜记作菜 $i$。 如果他将四道菜按顺序排列为 $2, 3, 1, 4$，那么一旦他吃了菜 $2$ 和 $3$，它们的总甜度为 $8$，大于 $7$。因此，在这种情况下，他最终会吃两道菜。 他吃的菜数不可能为 $1$ 或更少，所以输出 $2$。

标签: AtCoder|abc364C

来源

AtCoder|abc364C