#P88. 土拨鼠的盾牌

土拨鼠的盾牌

故事背景

一天,XX国和YY国由于不知什么原因而发起了战争。由于XX国科技发达,制造出了威力无比的导弹。而YY国自知打不过XX国,但又不肯投降,就只能将自己领土的损失降低。但导弹是不认人的。

幸亏,一名YY国的土拨鼠浚庭研制出了一个巨大的防御能力为 kk 的盾牌,可以防住一些导弹的攻击。但还有一些导弹威力实在太大,盾牌挡不住,而且盾牌能挡住的导弹也会给盾牌一定的损失。也就是说,假如盾牌原耐久为5,在防下导弹威力为3的导弹时耐久就变成了2,没法再防一个威力为4的导弹了。

所以,为了使YY国不受到更多伤害,土拨鼠浚庭想让你编程计算一下,他最多能防下多少导弹。

题目描述

给定XX国各个导弹的威力(注意,导弹的发射顺序也很重要,先发的导弹在前,后发的导弹在后,编程时不可以将它们的顺序打乱),以及土拨鼠浚庭研制的盾牌防御能力,计算出土拨鼠浚庭最多能防下多少导弹。

格式

输入

两行。

第一行为两个整数 nnkk。表示导弹的数量和盾牌最开始的防御能力。

输出

土拨鼠浚庭的盾牌最多能防多少导弹。

样例

5 10
6 4 5 1 2
3

提示

【样例1】说明:

盾牌最多能防下威力为4,5,1 或 4,1,2或5,1,2的导弹。

1n1061 \le n \le 10^6

1k1091 \le k \le 10^9