← 返回题目列表

AtCoder · arc057_b

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 次。

代表青木求出高桥心情好的最大天数。


制約

  • 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