Problem Statement

高橋君は $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$ 回ゲームに勝ったことを知っています。

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

Constraints

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

Input

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

N K
a_1
:
a_N

Output

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