問題文
高桥君 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