AT_arc057_b [ARC057B] 高橋君ゲーム

[problemUrl]: https://atcoder.jp/contests/arc057/tasks/arc057_b 高橋君は $ 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 $ 回ゲームに勝ったことを知っています。 青木君に代わって、高橋君の機嫌がよかった日数の最大値を求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ K $ $ a_1 $ : $ a_N $

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

### 制約 - $ 1\ ≦\ N\ ≦\ 2000 $ - $ 1\ ≦\ a_i\ ≦\ 500000(1\ ≦\ i\ ≦\ N) $ - $ 0\ ≦\ K\ ≦\ a_1+...+a_N $