AtCoder Regular Contest 057

B - 高橋君ゲーム


Time limit時間制限 : 2sec / Memory limitメモリ制限 : 262.144MB

問題文

高橋君は N 日にわたってゲームをしています。i(1 ≦ i ≦ N) 日目には、a_i 回のゲームをします。

各ゲームの結果は、勝つか負けるかのどちらかです。

高橋君の i(1 ≦ i ≦ N) 日目の機嫌は、勝率によって定まり、i-1 日目までの勝率より i 日目までの勝率のほうが真に高かった場合、i 日目に機嫌をよくします。そうでない場合、i 日目に機嫌を悪くします。 ただし、i 日目までの勝率とは、i = 0のとき 0 、そうでないときは i 日目までにゲームで勝った回数の合計を i 日目までにゲームをした回数の合計で割った値を指します。

高橋君の機嫌は AtCoder 社の収益に直結するので、青木君は高橋君の機嫌が気になります。青木君は、高橋君が N 日間で合計 K 回ゲームに勝ったことを知っています。

青木君に代わって、高橋君の機嫌がよかった日数の最大値を求めてください。


制約

  • 1 ≦ N ≦ 2000
  • 1 ≦ a_i ≦ 500000(1 ≦ i ≦ N)
  • 0 ≦ K ≦ a_1+...+a_N

入力

入力は以下の形式で標準入力から与えられる。

N K
a_1
:
a_N

出力

高橋君の機嫌がよかった日数の最大値を 1 行に出力せよ。


入力例1

5 7
2
3
7
4
9

出力例1

3

例えば 1,2,3,4,5 日目にそれぞれ 1,2,1,3,0 勝した場合、高橋君の機嫌がよい日数は 3 日になります。


入力例2

3 5
1
2
2

出力例2

1

入力例3

2 4
2
10

出力例3

1

入力例4

10 12
2
8
3
5
10
5
2
9
19
22

出力例4

7

Submit提出する