分数: 333 分
问题陈述
高桥是一名小学老师。今天是班级联欢会,他需要给孩子们分发糖果。
有 N 班里的孩子,还有孩子 如果他们准确收到, i (1 \leq i \leq N) 就会满意 S_i 糖果。如果他们收到的钱少于 S_i 糖果。
高桥共有 P 糖果。他将选择其中的一个子集 N 给孩子糖果。每个被选中的孩子 i 准确接收 S_i 糖果,没有被选中的孩子不会收到糖果。但所发放的糖果总数不得超过 P。完全不选择孩子是允许的,剩下的糖果也是允许的。
收到糖果的孩子总是满意的,没有收到糖果的孩子不满足。通过明智地选择要给糖果的儿童子集,最大化满意儿童的数量。
约束
- 1 \leq N \leq 2 \times 10^5
- 1 \leq P \leq 10^{18}
- 1 \leq S_i \leq 10^9 (1 \leq i \leq N)
- 所有输入均为整数。
输入
N P S_1 S_2 \ldots S_N
- 第一行包含一个整数 N 代表孩子的数量和一个整数 P 代表高桥拥有的糖果总数,以空格分隔。
- 第二行包含整数 S_1, S_2, \ldots, S_N 代表每个孩子需要满足的糖果数量,用空格分隔。
输出
在一行上打印满意儿童的最大数量。
样本输入 1
5 10 3 1 4 2 5
示例输出 1
4
示例输入 2
7 20 5 3 8 2 6 1 4
示例输出 2
5
示例输入 3
10 1000000000000 500000000 100000000 300000000 200000000 400000000 150000000 250000000 50000000 350000000 450000000
示例输出 3
10