1185: 点球大战

Memory Limit:128 MB Time Limit:1.000 S
Judge Style:Text Compare Creator:
Submit:48 Solved:29

Description

$24$ 世纪某一年世界杯决赛上,法国和阿根廷经过了 $90$ 分钟的常规比赛和 $30$ 分钟的加时赛,最终进入了点球大战。

点球比赛规则为:双方各有 $n$ 名球员踢点球,并且本着”赛出风采“的赛事理念,即便罚点球过程中胜负已分都会让所有球员罚完。

法国门将 Ken 是个十分自私的家伙,他也不在乎是否能帮助队伍获胜,只希望自己能扑出的点球越多越好。

Ken 只能扑出罚点球能力低于或者等于自己体力的球员踢出的点球。

点球大战开始前 Ken 的体力仅剩 $m$,然而他有着神奇的能力:

在任意一轮:

- 如果 Ken 选择扑救,会消耗与该对手罚点球能力相当的体力;
- 如果 Ken 选择不扑救,在进入下一轮点球前能恢复与该对手罚点球能力相当的体力。

Ken 在赛前通过私家侦探提前获取了对手 $n$ 名球员罚点球的顺序以及他们的罚点球能力,请问 Ken 应该采取怎么样的扑点球策略才能使得自己扑出尽可能多的点球呢?

Input

共 $2$ 行。

第一行,包含 $2$ 个正整数 $n$ 和 $m$,分别表示对手球员数量和 Ken 的初始能力值。

第二行,包含 $n$ 个整数,中间以空格隔开,表示对方按顺序罚点球的 $n$ 名球员的罚点球能力。

Output

输出最多的扑点球数量。

Sample Input Copy

3 25
25 10 15

Sample Output Copy

2

HINT

数据范围:

对于 $100\%$ 测试点,$5 \le n\le 20$,$ 0 \lt m\le 1000$,任意一对手罚点球能力均小于等于 $1000$。

Source/Category