Problem Description

Takahashi is playing a game over $ N $ days. On the $i(1\ ≦\ i\ ≦\ N)$ day, he plays $ a_i $ games.

Each game results in either a win or a loss.

Takahashi's mood on the $i(1\ ≦\ i\ ≦\ N)$ day is determined by his win rate. If his win rate up to the $ i $ day is strictly higher than his win rate up to the $ i-1 $ day, he will be in a good mood on the $ i $ day. Otherwise, he will be in a bad mood on the $ i $ day. The win rate up to the $ i $ day is defined as $ 0 $ when $i\ =\ 0$, and otherwise as the total number of wins up to the $ i $ day divided by the total number of games played up to the $ i $ day.

Since Takahashi's mood directly affects the revenue of AtCoder Inc., Aoki is concerned about Takahashi's mood. Aoki knows that Takahashi won a total of $ K $ games over the $ N $ days.

Please find the maximum number of days when Takahashi's mood was good on behalf of Aoki.

Input Format

The input is given from the standard input in the following format:

$ N $ $ K $ $ a_1 $ : $ a_N $

Output Format

Output the maximum number of days when Takahashi's mood was good in one line.

Sample Input and Output

Sample Input #1

5 7
2
3
7
4
9

Sample Output #1

3

Sample Input #2

3 5
1
2
2

Sample Output #2

1

Sample Input #3

2 4
2
10

Sample Output #3

1

Sample Input #4

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

Sample Output #4

7

Notes/Hints

Constraints

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

见题面 Input 部分

见题面 Output 部分