题目描述

回转寿司是一种很有特色的餐饮服务.店家会把寿司放在一条环形传送带上.随着传送带的缓缓转动,寿司就会转到食客面前.有一家回转寿司餐厅为了招揽生意,邀请了一位大胃王来店里表演吃寿司.

大胃王在环形的传送带上任意选择一个座位坐下.然后传送带就会开动.传送带上有n盘寿司,编号为[1,2,3......n]

如果大胃王吃下编号为i的寿司,那么他下一盘要吃的寿司编号为i+1,不准跳着吃.如果大胃王吃下编号为n的寿司,那么他下一盘要吃的寿司编号为1(因为传送带是环状的)

大胃王每吃下一盘寿司,都会积累少量的辐射伤害.大胃王最多能抵抗m点辐射伤害.请问大胃王最多能吃多少盘寿司?

输入格式

第一行输入两个整数n,m,分别代表传送带上总共有n盘寿司和大胃王的辐射抵抗值是m点

第二行输入n个整数$a_i$,代表编号为i的寿司的辐射伤害.

输出格式

输出一个整数,代表大胃王最多能吃多少盘寿司

样例输入/输出

6 5
2 2 2 2 2 2

2

7 8
1 9 1 1 9 1 1

3

7 8
1 9 1 1 4 1 1

5

数据规模与提示

样例解析2:大胃王吃了6号,7号,1号寿司

样例解析3:大胃王吃了3号,4号,5号,6号,7号寿司;也可以吃4号,5号,6号,7号,1号寿司

30%数据: $1 ≤ n ≤ 10^2;1 ≤ m ≤ 10^2;1 ≤ a_i ≤ 10$

60%数据:$1 ≤ n ≤ 10^4;1 ≤ m ≤ 10^4;1 ≤ a_i ≤ 10$

80%数据:$1 ≤ n ≤ 10^5;1 ≤ m ≤ 10^5;1 ≤ a_i ≤ 10$

100%数据:$1 ≤ n ≤ 10^6;1 ≤ m ≤ 10^9;1 ≤ a_i ≤ 10^6$

时间限制：1000ms.

内存限制：256MB.