問題文

高橋君は $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