1887: 阿拉德的冒险者

内存限制：128 MB 时间限制：1.000 S
评测方式：文本比较 命题人：
提交：262 解决：11

题目描述

在阿拉德大陆上有n块区域，艾尔文防线、赫顿玛尔、魔界、神界、雾隐之地……作为冒险者的你想以一种既定的路线（即从1到n）去畅游这n个大陆，但由于这n块区域常有战争发生，因此每到一块区域你都需要消耗 ai 点能量来帮助恢复和平后再进行畅游。不过任何力量的使用都要付出代价，你只有 k 次释放能量的机会来帮助你所到达的区域恢复安宁，且释放能量时不消耗任何生命力。你在冒险前拥有 m 点生命力 ，若你在冒险中不幸用完全部的生命力，则会回到你诞生的地方陷入沉睡。现在请问你最多可以畅游多少个大陆。


注意 : 若在当前区域消耗完生命力则意味着你并没有畅游该国家

输入

输入包含 2 行 。
第一行三个正整数 n , m , k （1 <= n <= 2e4 , 1 <= m <= 1e9 , 0 <= k <= 2e4），
分别代表区域的个数 ， 你拥有的初始生命力 ， 你可以释放能量的次数。
第二行包含 n 个正整数 , 第 i 个正整数ai（1 <= ai <= 1e9）代表你不释放能量帮助第 i 个区域需要消耗的生命力大小

输出

输出包含一行 ，共一个整数 ， 表示你能畅游的国家的个数 。

样例输入 复制 

3 10 1
11 2 1

样例输出 复制 

3

提示

请注意看主页通知下面的提示

来源/分类