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: $d_1, d_2, \dots, d_n$ ($-10^6 \le d_i \le 10^6$). The $i$-th element means that monster's hp (hit points) changes by the value $d_i$ 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 + d_i$.

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 \le H \le 10^{12}$, $1 \le n \le 2\cdot10^5$). The second line contains the sequence of integers $d_1, d_2, \dots, d_n$ ($-10^6 \le d_i \le 10^6$), where $d_i$ 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

Difficulty: introductory

Starter code:

Solutions:
H, n = list(map(int, input().split()))
d = list(map(int, input().split()))

t = 0
miPt = H
for a in d:
  t += 1
  H += a
  miPt = min(miPt, H)
  if H <= 0:
    print(t)
    return

if sum(d) >= 0:
  print(-1)
  return

jump = max(0, miPt // -sum(d) - 2)
H -= jump * -sum(d)
t += n * jump
for i in range(100000000000000000):
  t += 1
  H += d[i % n]
  if H <= 0:
    print(t)
    return


from itertools import accumulate
import math

H, n = map(int, input().split())

d = list(map(int, input().split()))

acc = list(accumulate(d))
per_round = acc[-1]

m = min(acc)

if m >= 0:
	print(-1)
	return

target = -m

if H <= target:
	rounds = 0
elif per_round >= 0:
	print(-1)
	return
else:
	rounds = math.ceil((H - target) / -per_round)

health = H - rounds * -per_round

for i, diff in enumerate(acc):
	cur = health + diff
	if cur <= 0:
		break

minutes = rounds * n + i+1
print(minutes)

# -*- coding: utf-8 -*-
# @Time    : 2019/3/19 23:03
# @Author  : LunaFire
# @Email   : gilgemesh2012@gmail.com
# @File    : E. Superhero Battle.py


def main():
    total_hp, n = map(int, input().split())
    d = list(map(int, input().split()))

    c = d.copy()
    for i in range(1, n):
        c[i] += c[i - 1]

    for i in range(n):
        if total_hp + c[i] <= 0:
            print(i + 1)
            return

    if c[-1] >= 0:
        print(-1)
        return

    min_val, round_dmg = -min(c), -c[-1]
    # print(min_val, round_dmg)
    temp_round = (total_hp - min_val + (round_dmg - 1)) // round_dmg
    ret = temp_round * n
    total_hp -= temp_round * round_dmg
    for i in range(n):
        if total_hp + c[i] <= 0:
            ret += i + 1
            break
    print(ret)


def __starting_point():
    main()
__starting_point()

import math

def test(k):
    nonlocal sm, mn, h
    return h + k * sm + mn <= 0


h, n = map(int, input().split())
a = list(map(int, input().split()))
mn = math.inf
sm = 0
for e in a:
    sm += e
    mn = min(mn, sm)
if mn >= 0:
    print(-1)
    return
l = -1
r = h + 1
while r - l > 1:
    m = (r + l) // 2
    if test(m):
        r = m
    else:
        l = m
h += sm * r
if h <= 0:
    print(n * r)
    return
for i in range(n):
    h += a[i]
    if h <= 0:
        print(r * n + i + 1)
        return
print(-1)

import sys
from math import *

def minp():
	return sys.stdin.readline().strip()

def mint():
	return int(minp())

def mints():
	return list(map(int, minp().split()))

H, n = mints()
d = list(mints())
s = [0]*(n+1)
for i in range(n):
	s[i+1] = s[i]+d[i]
for i in range(n+1):
	if s[i] + H <= 0:
		print(i)
		return
#print(s)
if s[n] >= 0:
	print(-1)
else:
	l = -1
	r = H//(-s[n]) + 2
	while r-l > 1:
		c = (l+r)//2
		h = -c*s[n]-H
		z = -1
		for i in range(n+1):
			if s[i] <= h:
				z = i
				break
		if z == -1:
			l = c
		else:
			r = c
	h = -r*s[n]-H
	z = -1
	for i in range(n+1):
		if s[i] <= h:
			print(r*n+i)
			break


[H, n] = [int(x) for x in input().split()]
d = [int(x) for x in input().split()]

H_old = H
mH = H

for i in range(n):
  H += d[i]
  mH = min(mH, H)
  if H <= 0:
    print(i+1)
    break;
else:
  if H_old <= H:
    print(-1)
  else:
    df = H_old - H
    mD = H_old - mH
    rnds = (mH+df-1) // df
    H = H_old - rnds * df
    for i in range(n):
      H += d[i]
      if H <= 0:
        print(rnds*n + i+1)
        break;


H, n = list(map(int, input().split()))
ds = [int(x) for x in input().split()]

h = H
mn = 0
for i, d in enumerate(ds):
    h += d
    mn = min(mn, h - H)
    if h <= 0:
        print(i + 1)
        break
else:
    sd = sum(ds)
    if sd >= 0:
        print(-1)
    else:
        sd = -sd
        # print(mn, sd)
        repeat = (H + mn) // sd
        h = H - repeat * sd
        # print(repeat, h)
        for i, d in enumerate(ds):
            h += d
            if h <= 0:
                print(repeat * n + i + 1)
                break
        else:
            for i, d in enumerate(ds):
                h += d
                if h <= 0:
                    print(repeat * n + i + 1 + n)
                    break


# alpha = "abcdefghijklmnopqrstuvwxyz"
# prime = 998244353 
INF = 100_000_000
# from heapq import heappush, heappop
# from collections import defaultdict
t = 1#int(input())
# from math import sqrt


for test in range(t):
    # n = int(input())
    H, n = (list(map(int, input().split())))
    # a = []
    # for i in range(n):
    # l = input()
    # r = input()
    d = (list((list(map(int, input().split())))))
    pre = [0 for i in range(n+1)]

    minVal = pre[0]
    minInd = 0
    for i in range(n):
        pre[i+1] = pre[i]+d[i]
        if pre[i+1]<minVal:
            minInd = i+1
            minVal = pre[i+1]

    h = H
    ans = 0
    for i in d:
        ans+=1
        h+=i
        if h<=0:
            print(ans)
            return
    if pre[-1] >= 0:
        print(-1)
    else:
        h=H
        h+=minVal
        tmp = (h-pre[-1]-1)//(-pre[-1])
        # print(tmp, minVal, pre[-1])
        ans = tmp*(n)
        h=H
        h+= pre[-1]*tmp
        for i in d:
            ans+=1
            h+=i
            if h<=0:
                print(ans)
                break




    

            


from math import floor

(H, n) = (int(x) for x in input().split())
d = [int(x) for x in input().split()]

sum_d = sum(d)

max_damage_per_round = 0
damage_sofar = 0
for attack in d:
	damage_sofar += attack
	max_damage_per_round = min(max_damage_per_round, damage_sofar)

max_damage_per_round = abs(max_damage_per_round)

answer = 0

for attack in d:
	answer += 1
	H += attack
	if H <= 0:
		print(answer)
		return

if sum_d >= 0:
	print(-1)
	return

if H > max_damage_per_round:
	can_attack_rounds_count = floor((H - max_damage_per_round - 1) / abs(sum_d))
	answer += n * can_attack_rounds_count
	H += sum_d * can_attack_rounds_count

if H <= 0:
	print(answer)
	return

while True:
	for attack in d:
		answer += 1
		H += attack
		if H <= 0:
			print(answer)
			return

import math
h,n = map(int, input().strip().split())
l = list(map(int, input().strip().split()))
mn = 0
sm = 0
counter = 0
done = False
for i in l:
    counter += 1
    sm += i
    mn = min(mn,sm)
    if h + mn <= 0 and done == False:
        print(counter)
        done = True
if sm >= 0:
    if done == False:
        print (-1)
else:
    nh = h + mn
    it = nh//-sm
    if nh %-sm:
        it += 1
    ans = it*n
    h = h + it*sm
    for i in range(n):
        h = h + l[i]
        ans += 1
        if h <= 0 and done == False:
            print (ans)
            break

import sys
input = sys.stdin.readline

H,n=list(map(int,input().split()))
D=list(map(int,input().split()))

from itertools import accumulate
ONETURN=list(accumulate(D))

MIN=min(ONETURN)
ONE=ONETURN[-1]

if ONE>=0:
    if H+MIN>0:
        print(-1)
        return

    DAMAGED=[H+o for o in ONETURN]
    for i in range(n):
        if DAMAGED[i]<=0:
            print(i+1)
            return

ANS=0

R=max(0,(H+MIN)//(-ONE))
ANS+=R*n
H+=R*ONE

while H+MIN>0:
    H+=ONE
    ANS+=n

DAMAGED=[H+o for o in ONETURN]
for i in range(n):
    if DAMAGED[i]<=0:
        print(ANS+i+1)
        break


H, n = map(int, input().split())
D = list(map(int, input().split()))
for i in range(1, n):
    D[i] += D[i - 1]
w = -min(D)
if D[-1] >= 0 and w < H:
    print(-1)
    return
if D[-1] >= 0 or w >= H:
    for q in range(n):
        i = D[q]
        if -i >= H:
            print(q + 1)
            return
cnt = 0
cnt += n * ((H - w - D[-1] - 1) // (-D[-1]))
sas = H - cnt // n * (-D[-1])
for q in range(n):
    i = D[q]
    if -i >= sas:
        print(cnt + q + 1)
        break

H, n = (int(t) for t in input().split(' '))
d = [int(t) for t in input().split(' ')]

hp_diff = sum(d)

current_hp = 0
rip_hp_max = 0
for di in d:
    current_hp += di
    rip_hp_max = max(rip_hp_max, -current_hp)

if hp_diff < 0 and rip_hp_max < H:
    required_full_rounds = (H - rip_hp_max) // -hp_diff
else:
    required_full_rounds = 0

hp_after_full_rounds = H + required_full_rounds * hp_diff
current_hp = hp_after_full_rounds
for i in range(2*n):
    current_hp += d[i % n]
    if current_hp <= 0:
        print(i+1+required_full_rounds*n)
        return

print(-1)


h, n = list(map(int, input().split()))
fo = [int(x) for x in input().split()]
ac = [0]*n
miac = [0]*n
for i in range(n):
	ac[i] = ac[i-1]+fo[i]
	miac[i] = min(ac[i], miac[i-1])
# print(ac)
# print(miac)
m = min(ac)
if h + miac[-1] > 0 and ac[-1] >= 0:
	print(-1)
else:
	if h + miac[-1] <= 0:
		hi, lo = n-1, 0
		while hi > lo:
			mid = (hi+lo)//2
			if miac[mid]+h > 0:
				lo = mid+1
			else:
				hi = mid
		print(hi+1)
	else:
		bajo = (h+miac[-1]-1)//(-ac[-1]) +1
		# print(h)
		h += (bajo*ac[-1])
		# print(h)
		hi, lo = n-1, 0
		while hi > lo:
			mid = (hi+lo)//2
			if miac[mid]+h > 0:
				lo = mid+1
			else:
				hi = mid
		print(hi+1+ bajo*n)


''' CODED WITH LOVE BY SATYAM KUMAR '''

from sys import stdin, stdout
import cProfile, math
from collections import Counter
from bisect import bisect_left,bisect,bisect_right
import itertools
from copy import deepcopy
from fractions import Fraction
import sys, threading
import operator as op
from functools import reduce
sys.setrecursionlimit(10**6) # max depth of recursion
threading.stack_size(2**27)  # new thread will get stack of such size
fac_warmup = False
printHeap = str()
memory_constrained = False
P = 10**9+7
import sys

class merge_find:
    def __init__(self,n):
        self.parent = list(range(n))
        self.size = [1]*n
        self.num_sets = n
        self.lista = [[_] for _ in range(n)]
    def find(self,a):
        to_update = []
        while a != self.parent[a]:
            to_update.append(a)
            a = self.parent[a]
        for b in to_update:
            self.parent[b] = a
        return self.parent[a]
    def merge(self,a,b):
        a = self.find(a)
        b = self.find(b)
        if a==b:
            return
        if self.size[a]<self.size[b]:
            a,b = b,a
        self.num_sets -= 1
        self.parent[b] = a
        self.size[a] += self.size[b]
        self.lista[a] += self.lista[b]
    def set_size(self, a):
        return self.size[self.find(a)]
    def __len__(self):
        return self.num_sets

def display(string_to_print):
    stdout.write(str(string_to_print) + "\n")

def primeFactors(n): #n**0.5 complex 
    factors = dict()
    for i in range(2,math.ceil(math.sqrt(n))+1):  
        while n % i== 0: 
            if i in factors:
                factors[i]+=1
            else: factors[i]=1
            n = n // i 
    if n>2:
        factors[n]=1
    return (factors)

def fibonacci_modP(n,MOD):
    if n<2: return 1
    #print (n,MOD)
    return (cached_fn(fibonacci_modP, (n+1)//2, MOD)*cached_fn(fibonacci_modP, n//2, MOD) + cached_fn(fibonacci_modP, (n-1) // 2, MOD)*cached_fn(fibonacci_modP, (n-2) // 2, MOD)) % MOD

def factorial_modP_Wilson(n , p): 
    if (p <= n): 
        return 0
    res = (p - 1) 
    for i in range (n + 1, p): 
        res = (res * cached_fn(InverseEuler,i, p)) % p 
    return res 

def binary(n,digits = 20):
    b = bin(n)[2:]
    b = '0'*(20-len(b))+b
    return b

def isprime(n):
    """Returns True if n is prime."""
    if n < 4:
        return True
    if n % 2 == 0:
        return False
    if n % 3 == 0:
        return False
    i = 5
    w = 2
    while i * i <= n:
        if n % i == 0:
            return False
        i += w
        w = 6 - w
    return True
factorial_modP = []
def warm_up_fac(MOD):
    nonlocal factorial_modP,fac_warmup
    if fac_warmup: return
    factorial_modP= [1 for _ in range(fac_warmup_size+1)]
    for i in range(2,fac_warmup_size):
        factorial_modP[i]= (factorial_modP[i-1]*i) % MOD
    fac_warmup = True

def InverseEuler(n,MOD):
    return pow(n,MOD-2,MOD)

def nCr(n, r, MOD):
    nonlocal fac_warmup,factorial_modP
    if not fac_warmup:
        warm_up_fac(MOD)
        fac_warmup = True
    return (factorial_modP[n]*((pow(factorial_modP[r], MOD-2, MOD) * pow(factorial_modP[n-r], MOD-2, MOD)) % MOD)) % MOD

def test_print(*args):
    if testingMode:
        print(args)

def display_list(list1, sep=" "):
    stdout.write(sep.join(map(str, list1)) + "\n")

def display_2D_list(li):
    for i in li:
        print(i)
def prefix_sum(li):
    sm = 0
    res = []
    for i in li:
        sm+=i
        res.append(sm)
    return res

def get_int():
    return int(stdin.readline().strip())

def get_tuple():
    return map(int, stdin.readline().split())

def get_list():
    return list(map(int, stdin.readline().split()))
import heapq,itertools
pq = []                         # list of entries arranged in a heap
entry_finder = {}               # mapping of tasks to entries
REMOVED = '<removed-task>' 
def add_task(task, priority=0):
    'Add a new task or update the priority of an existing task'
    if task in entry_finder:
        remove_task(task)
    count = next(counter)
    entry = [priority, count, task]
    entry_finder[task] = entry
    heapq.heappush(pq, entry)

def remove_task(task):
    'Mark an existing task as REMOVED.  Raise KeyError if not found.'
    entry = entry_finder.pop(task)
    entry[-1] = REMOVED

def pop_task():
    'Remove and return the lowest priority task. Raise KeyError if empty.'
    while pq:
        priority, count, task = heapq.heappop(pq)
        if task is not REMOVED:
            del entry_finder[task]
            return task
    raise KeyError('pop from an empty priority queue')
memory = dict()
def clear_cache():
    nonlocal memory
    memory = dict()
def cached_fn(fn, *args):
    nonlocal memory
    if args in memory:
        return memory[args]
    else:
        result = fn(*args)
        memory[args] = result
        return result

def ncr (n,r):
    return math.factorial(n)/(math.factorial(n-r)*math.factorial(r))
def binary_serach(i,li):
    #print("Search for ",i)
    fn = lambda x: li[x]-x//i
    x = -1
    b = len(li)
    while b>=1:
        #print(b,x)
        while b+x<len(li) and fn(b+x)>0: #Change this condition 2 to whatever you like
            x+=b
        b=b//2
    return x

# -------------------------------------------------------------- MAIN PROGRAM
TestCases = False
testingMode = False
fac_warmup_size = 10**5+100
optimiseForReccursion = True #Can not be used clubbed with TestCases
from math import factorial

def main():
    hp,n = get_tuple()
    li = get_list()
    sm = prefix_sum(li)
    mn = min(sm) if min(sm)<0 else 0
    j = hp+mn
    if j>0 and sm[-1]>=0:
        print(-1)
        return
    #print(sm)
    tries = n*math.ceil(j//abs(sm[-1])) if j>0 else 0
    hp += sm[-1]*math.ceil(j//abs(sm[-1])) if j>0 else 0
    #print(tries,hp,j)
    while hp>0:
        hp+=li[tries%n]
        tries+=1
    print(tries)
    
# --------------------------------------------------------------------- END=


if TestCases: 
    for _ in range(get_int()): 
        cProfile.run('main()') if testingMode else main() 
else: (cProfile.run('main()') if testingMode else main()) if not optimiseForReccursion else threading.Thread(target=main).start()

H, n = list(map(int,input().split()))
hp = list(map(int,input().split()))
sum = H
mini = H
import sys
for i in range(n):
	sum = sum + hp[i]
	mini = min(mini, sum)
	if sum <= 0:
		print(i+1)
		return
if sum>=H:
	print(-1)
	return
x =1 + (mini-1) // (H-sum)

H = H - (H-sum)*x
wyn = n*x
for i in hp:
	wyn += 1
	H = H + i
	if H<=0:
		print(wyn)
		break


H,n=list(map(int,input().split()))
arr=list(map(int,input().split()))
arr1=[]
mostmin=10**9
val=0
mostminindex=-1
for i in range(n):
	val+=arr[i]
	arr1.append(val)
	if(mostmin>val):
		mostmin=val
		mostminindex=i
if(mostmin>=0):
	print(-1)
elif(abs(mostmin)<H and val>=0):
	print(-1)
else:
	turns=-1
	if(H+mostmin<=0):
		turns=0
	else:
		if(val!=0):
			turns=(H-abs(mostmin))//abs(val)
		else:
			turns=0
		#print(turns)
	H-=(abs(val)*turns)
	minutes=n*turns
	for i in range(n):
		if(H+arr1[i]<=0):
			print(minutes+1)
			return
		else:
			minutes+=1
	H-=abs(val)
	for i in range(n):
		if(arr1[i]+H<=0):
			print(minutes+1)
			return
		else:
			minutes+=1
	print(-1)



from sys import stdin

H,n=list(map(int,stdin.readline().split()))
arr=list(map(int,stdin.readline().split()))
k=H
d={}
pre=0
cond=False
for i in range(n):
    k+=arr[i]
    pre+=arr[i]
    if pre in d:
        d[pre].append(i+1)
    else:
        d[pre]=[i+1]
    if k<=0:
        ans=i+1
        cond=True
        break
    else:
        pass
if cond==True:
    print(ans)
else:
    s=sum(arr)
    if s<0:
        a=min(list(d.keys()))
        m=(H+a)//abs(s)
        H+=(s*m)
        ans=n*m
        while(H>0):
            l=list([x for x in list(d.keys()) if x+H<=0])
            if len(l)>0:
                case=[]
                for ele in l:
                    case.extend(d[ele])
                ans+=min(case)
                print(ans)
                break
            else:
                H+=s
                ans+=n
    else:
        print(-1)


import math
H, n = [int(i) for i in input().split(' ')]
d = [int(i) for i in input().split(' ')]
H_cur = H
dead = False
d_acc = [0]
for i in range(n):
    d_acc.append(d_acc[-1]+d[i])
    H_cur += d[i]
    if H_cur <= 0:
        print(i+1)
        dead = True
        break
if not dead:
    if d_acc[-1] >= 0:
        print(-1)
    else:
        d_acc_min = min(d_acc)
        r = int(math.ceil((H+d_acc_min)/-d_acc[-1]))
        H_cur = H+r*d_acc[-1]
        for i in range(n):
            H_cur += d[i]
            if H_cur <= 0:
                print(r*n+i+1)
                break

from itertools import accumulate
H, n = list(map( int, input().split()))
D = list( map( int, input().split()))
accD = list( accumulate(D))
d = sum(D)
m = min(accD)
ans = 0
now = H
if H + m <= 0:
    for i in range(n):
        ans += 1
        now += D[i]
        if now <= 0:
            break
elif d >= 0:
    ans = -1
else:
    ans = ((H+m)//(-d))*n
    now = H + (H+m)//(-d)*d
    while now > 0:
        for i in range(n):
            ans += 1
            now += D[i]
            if now <= 0:
                break
print(ans)


s1=list(map(int,input().split()))
s=list(map(int,input().split()))
h,n=s1[0],s1[1]
hp=h
time=0
mins=0
sums=0
for i in range(n):
    sums+=s[i]
    mins=min(mins,sums)
while time!=n:
    hp=hp+s[time]
    time+=1
    if hp<=0:
        break
if hp<=0:
    print(time)
else:
    t=sum(s)
    #print(t)
    if t>=0:
        print(-1)
    else:
        hp1=h+mins
        #print(hp1) 
        cycle=hp1//abs(t)
        #print(cycle) 
        time=n*(hp1//abs(t))
        #print(time) 
        timemod=0
        hp=h-abs(t)*cycle
        #print(hp)
        while hp>0:
            hp+=s[timemod]
            timemod=(timemod+1)%n
            time+=1
        print(time)
            
        
    
    


import sys
from math import ceil

fin = sys.stdin.readline
H, n = [int(elem) for elem in fin().split()]
d_list = [int(elem) for elem in fin().split()]
prefix_sum_d = [0] * n
cur_sum = 0
for i, d in enumerate(d_list):
    cur_sum += d
    prefix_sum_d[i] = cur_sum

# no point of death during the first round and the hp does not increase
max_damage_in_round = -min(prefix_sum_d)
if H - max_damage_in_round > 0 and prefix_sum_d[-1] >= 0:
    print(-1)
    return

damage_per_round = -prefix_sum_d[-1]
if H <= max_damage_in_round:
    num_rounds_before_death = 0
else:
    num_rounds_before_death = ceil((H - max_damage_in_round) / damage_per_round)

rest_H = H - damage_per_round * num_rounds_before_death
past_minutes = num_rounds_before_death * n

for additional_minutes, gain in enumerate(prefix_sum_d, start=1):
    if rest_H + gain <= 0:
        print(additional_minutes + past_minutes)
        break


h,n=map(int,input().split())
l=list(map(int,input().split()))
pref=[0]*(n+1)
ans=-1
for i in range(n):
         pref[i+1]=pref[i]+l[i]
         if(h+pref[i+1]<=0):
                  ans=i+1
                  break
if(ans!=-1 or pref[n]>=0):
         print(ans)
else:
         m=min(pref)
         x=abs((h+m)//pref[n])
         ans=n*x
         h+=x*pref[n]
    #     print(m,x,ans,h)
         for i in range(10*n):
                  h+=l[i%n]
                  ans+=1
                  if(h<=0):
                           print(ans)
                           break

h,n=map(int,input().split())
a=list(map(int,input().split()))
b=a[:]
H=h
for i in range(1,n):
    a[i]+=a[i-1]
t=0
for i in b:
    if H>0:
        H+=i
        t+=1
    else:
        print(t);return
if a[-1]>=0:
    print(-1);return()
else:
    r=min(a)
    m=(h+r)//abs(a[-1])
    h+=(m)*(a[-1])
    t=n*(m)
    while h>0:
        for i in b:
            if h>0:
                h+=i
                t+=1
            else:
                break
    print(t)