#812. 徐老师的心愿卡
徐老师的心愿卡
说明
石老师给了徐老师一张心愿卡,如果徐老师用这张心愿卡向石老师许愿,石老师就会实现他的愿望。
心愿卡有一个初始愿力值 $W$,每个心愿会消耗一定的愿力值。
如果一个心愿需要的愿力值超过了这张心愿卡的愿力值余额,石老师就不能实现徐老师的这个愿望,徐老师只能遗憾地放弃这个愿望了。
现在徐老师总共有 $n$ 个心愿,第 $i$ 个心愿需要消耗 $a_i$ 点愿力值,徐老师想知道他最多能实现几个心愿?
输入格式
第一行包含两个正整数 $n, W$,分别表示徐老师的心愿个数和心愿卡的初始愿力值。
第二行包含 $n$ 个正整数,由空格隔开,分别表示每个心愿需要消耗的愿力值。
对于 $20\%$ 的数据满足:$n \leq 10, a_i \leq 10, W \leq 100$
对于 $60\%$ 的数据满足:$n \leq 5000$
对于 $100\%$ 的数据满足:$n \leq 10^5, 1 \leq a_i \leq 10^4, 1 \leq W \leq 10^9$
输出格式
仅一行,包含一个正整数,表示徐老师最多能实现的愿望个数。
样例
5 4
3 4 2 8 1
2
相关
在下列比赛中: