GukiZ loves hiking in the mountains. He starts his hike at the height 0 and he has some goal to reach, initially equal to h.

The mountains are described by a sequence of integers A0,?A1,?...,?An?-?1. In the first day GukiZ will change his height by A0, in the second day by A1, and so on. Mountains are a regular structure so the pattern repeats after the first n days. In general, in the i-th day GukiZ will change his height by A(i?-?1)%n.

Additionally, GukiZ will become more and more tired and in the i-th day his goal will decrease by i. For example, after first three days his goal will be equal to h?-?1?-?2?-?3?=?h?-?6.

Note that A may contain negative elements, what rePResents going down from some hill. Moreover, GukiZ's height may become negative, and so does his goal!

You can assume that both GukiZ's height and goal change at the same moment (immediately and simultaneously) in the middle of a day.

Once GukiZ is at the height not less than his goal, he ends his hike. Could you calculate the number of days in his hike?

The first line of the input contains two integers n and h (1?≤?n?≤?105, 1?≤?h?≤?109) — the length of the array A and the initial goal, respectively. 

The second line contains n integers A0,?A1,?...,?An?-?1 (?-?109?≤?Ai?≤?109).

In a single line print the number of days in the GukiZ's hike.

It can be proved that for any valid input the answer exists.

3 457 -4 5output
7input
1 10output
1Note
GukiZ starts at height 0 with goal 45. We can describe his hike as follows:
After the first day he is at height 7 and his goal is 44. Height 3, goal 42. Height 8, goal 39. Height 15, goal 35. Height 11, goal 30. Height 16, goal 24. Height 23, goal 17. 
After the 7-th day Gukiz's height is not less than his goal so he ends his hike.
題意：
一個登山運動員，n座山，目標高度為h，然后給出n個數，運動員當前高度為前面所有山的高度和(注意山是重復的，第n座山后面是第一座山)。
同時，在第i天他的目標高度會見小i
當當前高度大于等于目標高度時，停止登山
求第幾天結束。
題解：
先判斷會不會在第一輪某一天就結束
如果沒有，那么假設進行x輪后結束，枚舉結束是在第x+i（1<=i<=n)天，然后對每個i算出最小的x，列一個不等式即可。
注意精度。
#include<iostream>#include<cstdio>#include<algorithm>#include<cstring>#include<vector>#include<queue>#include<stack>#include<cmath>using namespace std;#define rep(i,a,n) for (int i=a;i<n;i++)#define per(i,a,n) for (int i=n-1;i>=a;i--)#define pb push_back#define fi first#define se secondtypedef vector<int> VI;typedef long long ll;typedef pair<int,int> PII;const ll inf=0x3ffffffffffff;const ll mod=1000000007;const int maxn=1e5+10;ll a[maxn];ll sum=0;typedef long double db;int main(){    int n;    ll h;    scanf("%d%I64d",&n,&h);    rep(i,1,n+1) scanf("%I64d",&a[i]),sum+=a[i];    ll ans=inf;    ll h1=0;    rep(i,1,n+1)    {        h1+=a[i];        if(h1>=h-i*(i+1)/2)        {            printf("%d/n",i);            return 0;        }        db b=((db)i/n+1.0/2/n+(db)sum/n/n);        db c=((db)i*(i+1)/2-h+h1)/n/n;        db t=sqrtl(b*b-2*c);        t=t-b;        ans=min(ans,(ll)(i+ceill(t)*n));    }    printf("%I64d/n",ans);    return 0;}