CF1141E Superhero Battle

A superhero fights with a monster. The battle consists of rounds, each of which lasts exactly n minutes. After a round ends, the next round starts immediately. This is repeated over and over again.

Each round has the same scenario. It is described by a sequence of n numbers: d1,d2,…,dn(−10^6≤di≤10^6). The i-th element means that monster's hp (hit points) changes by the value didi during the i-th minute of each round. Formally, if before the i-th minute of a round the monster's hp is h, then after the i-th minute it changes to h:=h+di

The monster's initial hp is H. It means that before the battle the monster has H hit points. Print the first minute after which the monster dies. The monster dies if its hp is less than or equal to 0. Print -1 if the battle continues infinitely.

Input

The first line contains two integers H and n (1≤H≤10^12, 1≤n≤2⋅10^5). The second line contains the sequence of integers d1,d2,…,dn (−10^6≤di≤10^6), where di is the value to change monster's hp in the i-th minute of a round.

Output

Print -1 if the superhero can't kill the monster and the battle will last infinitely. Otherwise, print the positive integer k such that k is the first minute after which the monster is dead.

Examples

input

1000 6
-100 -200 -300 125 77 -4

output

9

input

1000000000000 5
-1 0 0 0 0

output

4999999999996

input

10 4
-3 -6 5 4

output

-1
题意解释：输入，给定了怪物的hp和n轮战斗对怪物造成的伤害。输出，怪物的hp降到0及以下即被击败输出第几分钟怪物被击败或-1.
解题思路：先判断第一个周期造成的最高伤害是多少和第一个周期是否对怪物造成了伤害，来确定怪物是否能被击败。然后我们通过计算求出到打败怪物的前一个周期的时间，再判断最后一个周期何时击败怪物。
其实可以说是个数学题，这里我用了二分来求解，但是long long精度不够，中间判断的时候将long long转为double来提高精度。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a[2000005];
int main()
{
    ll hp,n;
    scanf("%lld%lld%lld",&hp,&n,&a[1]);
    ll t=a[1];
    ll aa=0;
    ll mmin=min(t,aa);
    ll flag=1;
    for(int i=2;i<=n;++i)
    {
        scanf("%lld",&a[i]);
        t+=a[i];
        if(mmin>t)
        {
            mmin=t;
            flag=i;
        }
    }
    ll tmp=hp;
    tmp+=mmin;
    if(tmp<=0)
    {
        for(int i=1;i<=n;++i)
        {
            hp+=a[i];
            if(hp<=0)
            {
                cout<<i;
                return 0;
            }
        }
    }
    else
    {
        if(t>=0)
        {
            cout<<-1;
            return 0;
        }
        ll l=0,r=1000000000000;
        while(l<=r)
        {
            double mid=(l+r)/2;
            if(hp+(mid*t)+mmin<=0)
            {
                r=mid-1;
            }
            else
            {
                l=mid+1;
            }
        }
        hp+=l*t;    
        for(int i=1;i<=n;++i)
        {
            hp+=a[i];
            if(hp<=0)
            {
                cout<<i+l*n;
                return 0;
            }
        }
    }
}