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 应该采取怎么样的扑点球策略才能使得自己扑出尽可能多的点球呢?
点球比赛规则为:双方各有 $n$ 名球员踢点球,并且本着”赛出风采“的赛事理念,即便罚点球过程中胜负已分都会让所有球员罚完。
法国门将 Ken 是个十分自私的家伙,他也不在乎是否能帮助队伍获胜,只希望自己能扑出的点球越多越好。
Ken 只能扑出罚点球能力低于或者等于自己体力的球员踢出的点球。
点球大战开始前 Ken 的体力仅剩 $m$,然而他有着神奇的能力:
在任意一轮:
- 如果 Ken 选择扑救,会消耗与该对手罚点球能力相当的体力;
- 如果 Ken 选择不扑救,在进入下一轮点球前能恢复与该对手罚点球能力相当的体力。
Ken 在赛前通过私家侦探提前获取了对手 $n$ 名球员罚点球的顺序以及他们的罚点球能力,请问 Ken 应该采取怎么样的扑点球策略才能使得自己扑出尽可能多的点球呢?
Input
共 $2$ 行。
第一行,包含 $2$ 个正整数 $n$ 和 $m$,分别表示对手球员数量和 Ken 的初始能力值。
第二行,包含 $n$ 个整数,中间以空格隔开,表示对方按顺序罚点球的 $n$ 名球员的罚点球能力。
第一行,包含 $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$。
对于 $100\%$ 测试点,$5 \le n\le 20$,$ 0 \lt m\le 1000$,任意一对手罚点球能力均小于等于 $1000$。