Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

def main():
    N = int(input())
    A = list(map(int, input().split()))
    min_A = min(A)
    min_A_idx = A.index(min_A)
    A = A[min_A_idx:] + A[:min_A_idx]
    
    for s in range(A[0] * 2, -1, -2):
        mt = [None] * N
        mt[0] = s
        for n in range(N-1):
            if mt[n] > A[n+1] * 2:
                break
            mt[n+1] = (A[n+1] - mt[n]//2) * 2

        if mt[N-1] != None:
            if mt[N-1] //2 + mt[0] // 2 == A[0]:
                if min_A_idx == 0:
                    print(mt[-1], ' '.join(list(map(str, mt[:-1]))))
                    return
                print(' '.join(list(map(str, mt[N-min_A_idx-1:]))), ' '.join(list(map(str, mt[:N-min_A_idx-1]))))

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    N = int(input())
    A = list(map(int, input().split()))
    X = [None] * len(A)
    X[0] = sum(A) - 2 * sum([A[i] for i in range(1, len(A), 2)])
    for i in range(len(A)-1):
        X[i+1] = 2 * A[i] - X[i]
    
    print(' '.join(list(map(str, X))))
    
if __name__ == '__main__':
    main()
### BUGGY CODE ###

import collections
import math
N = int(input())
A = list(map(int, input().split()))
c = collections.Counter(A)

l = [math.factorial(i[1]) // (math.factorial(i[1]-2) * 2) for i in c.items() if i[1] > 1]
ans = sum(l)

for i in range(N):
  ans -= A.count(A[i])-1
  print(ans)
  ans = sum(l)

### FIXED CODE ###

import collections
N = int(input())
A = list(map(int, input().split()))
c = collections.Counter(A)
total = 1

for n in c.items():
  total += n[1]*(n[1]-1)//2

for i in range(N):
  print(total-c[A[i]])
### BUGGY CODE ###

N = int(input())
bit = 0
for i in range(N):
    a = int(input())
    bit = bit ^ 2 ** a

bit = str(bin(bit))

count = 0
for i in bit:
    if i == "1":
        count += 1

print(count)

### FIXED CODE ###

N = int(input())
L = []
for i in range(N):
    a = int(input())
    L.append(a)

L.sort()
ptr = 0
temp = 0
num = 1
ans = 0
while ptr < N:
    cc = L[ptr]
    f = 0
    while ptr < N and L[ptr] == cc:#同じ数字が続く終了条件
        f += 1
        ptr += 1
    ans += f%2

print(ans)
### BUGGY CODE ###


S = input()

s = list(S)

s.reverse()

#print (s)

lis = [0] * 13
lis[0] = 1
keta = 1

for i in range(len(S)):

    nlis = [0] * 13

    if s[i] == "?":

        for j in range(10):

            for k in range(13):

                nlis[ (k + (j * keta)) % 13] += lis[k]

    else:

        now = int(s[i])

        for k in range(13):

            nlis[ (k + (now * keta)) % 13 ] += lis[k]
            

    #print (nlis)
    keta *= 10
    for j in range(13):
        lis[j] = nlis[j] % (10**9 + 7)

#print (lis)
print (lis[5] % (10**9 + 7))


### FIXED CODE ###


S = input()

s = list(S)

s.reverse()

#print (s)

lis = [0] * 13
lis[0] = 1
keta = 1

for i in range(len(S)):

    nlis = [0] * 13



    for j in range(10):

        for k in range(13):

            if s[i]== "?" or j == int(s[i]):
                nlis[ (k + (j * keta)) % 13] += lis[k]

    keta *= 10
    keta = keta % 13
    for j in range(13):
        lis[j] = nlis[j] % (10**9 + 7)

#print (lis)
print (lis[5] % (10**9 + 7))
### BUGGY CODE ###

class SegTree:
    """ segment tree with point modification and range product. """
    # # https://yukicoder.me/submissions/452850
    def __init__(self, N, data_f = min, data_unit=1<<30):
        self.N = N
        self.data_f = data_f
        self.data_unit = data_unit
        self.data = [self.data_unit] * (N + N)

    def build(self, raw_data):
        data = self.data
        f = self.data_f
        N = self.N
        data[N:] = raw_data[:]
        for i in range(N - 1, 0, -1):
            data[i] = f(data[i << 1], data[i << 1 | 1])

    def set_val(self, i, x):
        data = self.data
        f = self.data_f
        i += self.N
        data[i] = x
        while i > 1:
            data[i >> 1] = f(data[i], data[i ^ 1])
            i >>= 1

    def fold(self, L, R):
        """ compute for [L, R) """
        vL = vR = self.data_unit
        data = self.data
        f = self.data_f
        L += self.N
        R += self.N
        while L < R:
            if L & 1:
                vL = f(vL, data[L])
                L += 1
            if R & 1:
                R -= 1
                vR = f(data[R], vR)
            L >>= 1
            R >>= 1
        return f(vL, vR)
      
N,Q=map(int,input().split())
*C,=map(int,input().split())
seg = SegTree(N,set.union,set())
seg.build([set([C[i]]) for i in range(N)])
for i in range(Q):
  l,r = map(int,input().split())
  print(len(seg.fold(l-1,r)))

### FIXED CODE ###

from time import time
start = time()

# 解説放送の解法

class BIT:
    '''https://tjkendev.github.io/procon-library/python/range_query/bit.html'''
    def __init__(self, n):
        self.n = n
        self.data = [0]*(n+1)
        self.el = [0]*(n+1)
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.data[i]
            i -= i & -i
        return s
    def add(self, i, x):
        self.el[i] += x
        while i <= self.n:
            self.data[i] += x
            i += i & -i
    def query(self, i, j=None):
        if j is None:
            return self.el[i]
        return self.sum(j) - self.sum(i)
      
def main():
  N,Q=map(int,input().split())
  *C,=map(int,input().split())
  q = [tuple(map(int,input().split())) for _ in range(Q)]

  # 重複度を数える。
  res=[]
  tmp_dict={}
  for i in range(N):
    if tmp_dict.get(C[i]) != None:
      #(クエリの種類、l, r）
      res.append((tmp_dict[C[i]]<<40) | (Q<<20) | i)
      del tmp_dict[C[i]]
    tmp_dict[C[i]] = i

  # クエリと合わせてソート。
  X = []
  for i in range(Q):
    l,r = q[i]
    # (元のクエリの順番、l, r)
    X.append(((l-1)<<40) | (i<<20) | r-1)
    
  X.extend(res) 
  X = sorted(X)

  # 平面走査
  bit = BIT(N)
  ans=[0]*Q
  mask = (1<<20) - 1
  for l in reversed(X):
    r = l & mask
    l >>= 20
    idx = l & mask
    l >>= 20
    if idx == Q:
      bit.add(r,1)
    else:
      ans[idx] = r-l+1-bit.query(l-1,r)
      
  print(*ans)
  
if __name__=="__main__":
  main()
### BUGGY CODE ###

n=int(input())
a=sorted(list(map(int,input().split())))
ans=1
b=[0]*(a[-1]-a[0]+2)
if a[0]==a[-1]:
  print(n)
else:
  for i in range(a[0]-1,a[-1]+1):
    b[i-a[0]+1]=a.count(i)
  for i in range(n+1):
    ans=max(ans,sum(b[i:i+3]))
  print(ans)

### FIXED CODE ###

import collections
n=int(input())
a=list(map(int,input().split()))
c=collections.Counter(a)
ans=1
for i in range(min(a),max(a)+1):
  goukei=c[i-1]+c[i]+c[i+1]
  ans=max(ans,goukei)
print(ans)
### BUGGY CODE ###

# ABC139E - League
from collections import deque


def main():
    N, *A = map(int, open(0).read().split())
    B = {}
    for i in range(N):
        x = i * (N - 1)
        B[i + 1] = deque(A[x : x + N - 1])
    ans, flg, matched = 0, 0, set()
    while B:
        for i in list(B.keys()):
            if i in B and i not in matched:
                x = B[i][0]
                if x in B and x not in matched and B[x][0] == i:
                    B[i].popleft(), B[x].popleft()
                    matched |= {i, x}
                    flg = 1
                    if not B[i]:
                        del B[i]
                    if not B[x]:
                        del B[x]
        if flg:
            ans += 1
            flg, matched = 0, set()
        else:
            print(-1)
            return
    print(ans)


if __name__ == "__main__":
    main()

### FIXED CODE ###

# ABC139E - League
from collections import deque


def main():
    N, *A = map(int, open(0).read().split())
    B = {}
    for i in range(N):
        x = i * (N - 1)
        B[i + 1] = deque(A[x : x + N - 1])
    ans, cnt, matched = 0, 0, set()
    q = [i for i in range(1, N + 1)]
    while q:
        ans += 1
        next_q = []
        for i in q:
            if i in B and i not in matched:
                x = B[i][0]
                if x in B and x not in matched and B[x][0] == i:
                    B[i].popleft(), B[x].popleft()
                    matched |= {i, x}
                    cnt += 1
                    if not B[i]:
                        del B[i]
                    else:
                        next_q += [i]
                    if not B[x]:
                        del B[x]
                    else:
                        next_q += [x]
        q = next_q
        matched = set()
    flg = cnt == N * (N - 1) // 2
    print(ans if flg else -1)


if __name__ == "__main__":
    main()
### BUGGY CODE ###

import itertools
import sys
input = sys.stdin.readline
n,k = map(int,input().split())
p = list(map(int,input().split()))
lstp = [0]*(n-k+1)
for i in range(n-k+1):
    lstp[i] = (0.5*(sum(p[i:i+k])+k))
print("{:.6f}".format(max(lstp)))

### FIXED CODE ###

n,k = map(int,input().split())
p = list(map(int,input().split()))
wa = sum(p[0:k])
next_wa = wa
for i in range(n-k):
    next_wa = next_wa - p[i] + p[i+k]
    if  next_wa > wa:
        wa = next_wa
print(0.5*(wa+k))
### BUGGY CODE ###

n = int ( input() )

def find_gcd(x, y): 
      
    while(y): 
        x, y = y, x % y 
      
    return x 

dicts = {}
total = 0 
for i in range(1, n + 1):
    for j in range(1, n + 1):
        for k in range(1, n + 1):
            strin = str(i) + "," + str(j)
            if strin not in dicts:
                gh = find_gcd(i, j)
                strin3 = str(j) + "," + str(i)
                dicts[strin] = gh 
                dicts[strin3] = gh 
                
            else:
                gh = dicts[strin]
            
            strin2 = str(gh) + "," + str(k)
            
            if strin2 not in dicts:
                gh = find_gcd(gh, k)
                strin4 = str(k) + "," + str(gh)
                dicts[strin2] = gh 
                dicts[strin4] = gh 
            else:
                gh = dicts[strin2]
            
            
            total += gh 
print(total)
                        


### FIXED CODE ###

n = int ( input() )

def find_gcd(x, y): 
      
    while(y): 
        x, y = y, x % y 
      
    return x 

dicts = {}
total = 0 
storedict = {}
for i in range(1, n + 1):
    for j in range(1, n + 1):
        
        strin = str(i) + "," + str(j)
        if strin not in dicts:
            gh = find_gcd(i, j)
            strin3 = str(j) + "," + str(i)
            dicts[strin] = gh 
            dicts[strin3] = gh 
            
        else:
            gh = dicts[strin]
        
        if gh not in storedict:
            storedict[gh] = 1 
        else:
            storedict[gh] += 1 

for k in range( 1 , n + 1):
    for key, value in storedict.items():
        gh = find_gcd(key, k)
        
        strin2 = str(gh) + "," + str(k)
        
        if strin2 not in dicts:
            gh = find_gcd(gh, k)
            strin4 = str(k) + "," + str(gh)
            dicts[strin2] = gh 
            dicts[strin4] = gh 
        else:
            gh = dicts[strin2]
            
        ans1 = gh * value    
        total += ans1 
print(total)
### BUGGY CODE ###

#coding: utf-8
s = str(input())
child = [1] * len(s)
# for j in range(len(s)):
# 	child[j] = 1

for j in range(10 ** 100):
	after = [0] * len(s)
	for i in range(len(s)):
		# print(i)
		if child[i] != 0:
			if s[i] == 'R':
				after[i+1] = after[i+1] + child[i]
				# child[i] = 0
			elif s[i] == 'L':
				after[i-1] = after[i-1] + child[i]
				# child[i] = 0
	child = after

print(child) 


### FIXED CODE ###

#coding: utf-8
s = str(input())
child = [0] * len(s)
# for j in range(len(s)):
# 	child[j] = 1
r = 0
l = 0
# lIdx = 0
rIdx = 0

for i in range(len(s)):
	# print(str(r)+","+str(l))
	if s[i] == 'R':
		# print(i)
		r = r+1
		if s[i+1] == 'L':
			rIdx = i
	elif s[i] == 'L':
		l = l+1
		if i == len(s)-1 or s[i+1] == 'R':
			#1セットが終了する
			# print('r='+str(r)+" l="+str(l))
			if ((r+l)%2) == 0:
				child[rIdx] = (r+l)//2
				child[rIdx+1] = (r+l)//2
			else:
				if r%2==0:
					child[rIdx+1] = (r+l)//2 + 1
					child[rIdx] = (r+l)//2
				else:
					child[rIdx+1] = (r+l)//2
					child[rIdx] = (r+l)//2 + 1
			r = 0
			l = 0
			# lIdx = i-1
# child[rIdx-1] = l

#roop終わらない解法
# for j in range(10 ** 100):
# 	after = [0] * len(s)
# 	for i in range(len(s)):
# 		# print(i)
# 		if child[i] != 0:
# 			if s[i] == 'R':
# 				after[i+1] = after[i+1] + child[i]
# 				# child[i] = 0
# 			elif s[i] == 'L':
# 				after[i-1] = after[i-1] + child[i]
# 				# child[i] = 0
# 	child = after

print(" ".join(map(str,child)))
### BUGGY CODE ###

import re
N=int(input());S=input()

def same_check(index,number):
    while index-number>=0:
        pattern=S[index-number:index+1]
        match_list=re.findall(pattern,S[:index+1])
        if len(match_list)==1:
            return number
        else:
            number+=1

number=0
for i in range(N):
    number=same_check(i,number)
print(number)

### FIXED CODE ###

n=int(input());s=input()

a=0
i=0
j=1
while j<n:
    if s[i:j] in s[j:]:
        a=max(a,j-i)
        j+=1
    else:
        i+=1

    if i==j:
        i+=1
        j+=2
print(a)
### BUGGY CODE ###

import collections
n = map(int, raw_input().split(' '))
ais = map(int, raw_input().split(' '))
cc = collections.Counter(ais)
ais.sort()
forbidden = set([])
j = 0
count =0
while(j < len(ais)):
	
	if cc[ais[j]] == 1: 
		flag = True
		for d in range(1,int(ais[j] ** 0.5) +1):
			if ais[j] % d == 0:
				if (d in forbidden) or ((ais[j]/d) in forbidden) :
					flag = False
					break
		count +=1 if flag else 0
	forbidden.add(ais[j])
	j+=1

print count

### FIXED CODE ###

import collections
n = map(int, raw_input().split(' '))
ais = map(int, raw_input().split(' '))
cc = collections.Counter(ais)
ais.sort()
m = max(ais)
p = [True for _ in range(m + 1)]

count = 0
for ai in ais:
	if p[ai] is True:
		x = 2 * ai
	 	while(x < len(p)): 
	 		p[x] = False
	 		x += ai
for ai in ais:
	if p[ai] is True:
		if cc[ai] == 1:
			count +=1
print count
### BUGGY CODE ###

from bisect import bisect
from bisect import bisect_left
N,K = map(int,input().split())
A = list(map(int,input().split()))

N = 2*10**5
K = 10000
A = [10**9]*(N//2)+[-10**9]*(N//2)

A.sort()



def count(m):
    res = 0
    for i in range(N):
        a = A[i]
        if a==0:
            if m>=0:
                res += N
        elif a>0:
            r = m/a
            j = bisect(A,r)
            res += j
        else:
            r = m/a
            j = bisect_left(A,r)
            res += N-j
        if a**2<=m:
            res -= 1
    res //= 2
    return res

def count1(m):
    res = 0
    cand = -10**19
    for i in range(N):
        a = A[i]
        if a==0:
            if m>=0:
                res += N
        elif a>0:
            r = m/a
            j = bisect(A,r)
            res += j
            if j!= 0:
                cand = max(cand,a*A[j-1])
        else:
            r = m/a
            j = bisect_left(A,r)
            res += N-j
            if j != N:
                cand = max(cand,a*A[j])
        if a**2<=m:
            res -= 1
    res //= 2
    return res,cand


l = -10**18
r = 10**18
m = (l+r)/2
for i in range(65):
    k = count(m)
    if k < K:
        l = m
    else:
        r = m
    m = (l+r)/2
k,ans = count1(r)
print(ans)

### FIXED CODE ###

N,K = map(int,input().split())
A = list(map(int,input().split()))

A = [A[i] for i in range(N) if A[i]!=0]
c = (N+len(A)-1)*(N-len(A))
N = len(A)
A.sort()
B = A[::-1]

def count(m):
    res = 0
    if m>=0:
        res += c
        j = N
        for i in range(N):
            if A[i]>0:
                break
            while j>0:
                if A[i]*A[j-1]<=m:
                    j -= 1
                else:
                    break
            res += N-j
        if A[i]>0:
            j = N-1
            for i in range(i,N):
                while j>=0:
                    if A[i]*A[j]>m:
                        j -= 1
                    else:
                        break
                res += j+1
    else:
        j = 0
        for i in range(N):
            if B[i]<0:
                break
            while j<N:
                if B[i]*B[j]>m:
                    j += 1
                else:
                    break
            res += N-j
        if B[i]<0:
            j = -1
            for i in range(i,N):
                while j<N-1:
                    if B[i]*B[j+1]<=m:
                        j += 1
                    else:
                        break
                res += j+1
    for i in range(N):
        if A[i]*A[i]<=m:
            res -= 1
    res //= 2
    return res

ng = -10**18
ok = 10**18
m = (ng+ok)//2
if N==0:
    ans = 0
else:
    for n in range(100):
        if count(m)<K:
            ng = m
        else:
            ok = m
        m = (ng+ok)//2
    ans = int(ok)
print(ans)
### BUGGY CODE ###

import sys
N=int(input())
a = list(map(int,input().split()))
cnt=0
j=0
if((1 in a)==False):
    print(-1)
    sys.exit()
i=1
while(a):
    if(a[0]!=i):
        cnt+=1
        a.pop(0)
    elif(a[0]==i):
        i+=1
        a.pop(0)


print(cnt)




### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
counter=0
n=1
for a in A:
    if(a == n):
        n+=1
    else:
        counter+=1

print(counter) if(n != 1) else print(-1)
### BUGGY CODE ###

n, k = map(int, input().split())
s = list(map(int,input()))

a = []
x = 0 #1の個数
y = 0 #0の個数
for i in range(n):
  if s[i] == 1:
    x += 1
  else:
    y += 1
  if x > 0 and y > 0:
    if s[i] == 0:
      a.append(x)
      x = 0
    else:
      a.append(-y)
      y = 0
if x > y:
  a.append(x)
else:
  a.append(-y)

m = len(a)
ans = [] #2k+1個の和
for i in range(m):
  x = 0
  flag = 0
  for j in range(m - i):
    if flag < k:
      if a[i+j] > 0:
        x += a[i+j]
      else:
        x += -a[i+j]
        flag += 1
    if flag == k and a[i+j] >0:
      x += a[i+j]
      flag += 1
  ans.append(x)
print(max(ans))

### FIXED CODE ###

n, k = map(int, input().split())
s = list(map(int,input()))

a = []
x = 0 #1の個数
y = 0 #0の個数
if s[0] == 0:
  a.append(0)
for i in range(n):
  if s[i] == 1:
    x += 1
  else:
    y += 1
  if x > 0 and y > 0:
    if s[i] == 0:
      a.append(x)
      x = 0
    else:
      a.append(y)
      y = 0
if x > y:
  a.append(x)
else:
  a.append(y)
  a.append(0)


m = len(a)
left=[0]*(m+1)
right=[0]*(m+1)

for i in range(m):
  left[i+1] = left[i] + a[i]
for i in range(m):
  right[m-i-1] = right[m-i] + a[m-i-1]

ans = 0
if m%2 == 0:
  r = int(m/2) + 1
else:
  r = int((m+1)/2) 
#print(r,a,right,left)
for i in range(r):
  if 2*i+2*k+1 <= m:
    x = left[2*i+2*k+1]-left[2*i]
  else:
    x = left[-1] - left[2*i]
  if ans < x:
    ans = x
print(ans)
### BUGGY CODE ###

N,Q = map(int, input().split())
S = input()
q_list = list()
for i in range(Q):
  l, r = map(int, input().split())
  q_list.append([l, r])

for i in range(Q):
  l = q_list[i][0]
  r = q_list[i][1]
  s = S[l-1:r]
  s_list= s.split('AC')
  print(len(s_list)-1)

### FIXED CODE ###

import sys
sy = sys.stdin.readlines()
N,Q = map(int, sy[0].split())
S = sy[1]
ACindex = [0 for _ in range(N+1)]
count = 0
for n in range(1, N):
  if S[n-1]=="A" and S[n]=="C":
    count += 1
  ACindex[n+1] = count

for i in range(Q):
  l, r = map(int, sy[2+i].split())
  print(ACindex[r]-ACindex[l])
### BUGGY CODE ###

N,K = map(int,input().split())
D = list(map(int,input().split()))
num = {0,1,2,3,4,5,6,7,8,9}
Ds = set(D)
diff = num^Ds
ans = N
while True:
    strN = str(N)
    flag = False
    for i in strN:
        if int(i) not in diff:
            flag = True
    if flag:
        ans += 1
    else:
        break
print(ans)

### FIXED CODE ###

N,K = map(int,input().split())
D = input().split()
num = set([str(i) for i in range(10)])
Ds = set(D)
diff = num^Ds
ans = N
while True:
    strN = set(list(str(ans)))
    if strN - diff:
        ans += 1
    else:
        break
print(ans)
### BUGGY CODE ###

numOp = int(input())
intList = list(map(int, input().split()))
mark = False


for i in range(numOp):
    if intList.count(intList[i]) != 1:
        mark = True
        print('NO')
        break
    else:
        mark = False

if not mark:
    print('YES')


### FIXED CODE ###

numOp = int(input())
intList = list(map(int, input().split()))

intList.sort()
for i in range(numOp):
    if intList[i] == intList[i - 1]:
        print('NO')
        break
    elif i == (numOp - 1):
        print('YES')
### BUGGY CODE ###

N, M = map(int, input().split())
for i in range(M//N, 0, -1):
    if M % i == 0:
        print(i)
        break

### FIXED CODE ###

def div(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    divisors.sort()
    return divisors

N, M = map(int, input().split())
for i in reversed(div(M)):
    if i <= M//N:
        print(i)
        break
### BUGGY CODE ###

X, Y = map(int, input().split())
n = (2 * X - Y) / 3
m = (2 * Y - X) / 3

if n < 0 or m < 0 or not n.is_integer() or not m.is_integer():
    print(0)
    exit()

n, m = map(int, [n, m])
mod = 10**9 + 7
fact = [1]
inv = [1]
for i in range(1, X + Y + 1):
    fact.append((fact[i-1] * i) % mod)
    inv.append(pow(fact[-1], mod-2, mod))

def cmb(n, r):
    return fact[n] * inv[n-r] * inv[r]

print(cmb(n+m, min(n, m)) % mod)



### FIXED CODE ###

X, Y = map(int, input().split())
n = (2 * X - Y) / 3
m = (2 * Y - X) / 3

if n < 0 or m < 0 or not n.is_integer() or not m.is_integer():
    print(0)
    exit()

n, m = map(int, [n, m])
mod = 10**9 + 7
fact = [1]
inv = [1]
for i in range(1, X + Y + 1):
    fact.append((fact[i-1] * i) % mod)
    inv.append(pow(fact[-1], mod-2, mod))

def cmb(n, r):
    return fact[n] * inv[n-r] * inv[r]

print(cmb(n+m, min(n, m)) % mod)
### BUGGY CODE ###

N , K = map(int,input().split())
Lum = list(map(int,input().split()))

K = min(K,41)
for i1 in range(K):
    B = [0]*N
    for i in range(N):
        l = max(0,i-Lum[i])
        r = min(N-1,i+Lum[i])
        B[l]+=1
        if r+1<N:
            B[r+1]-=1
    for i in range(1,N):
        B[i]+=B[i-1]
    Lum = B
    
Lum = [str(l) for l in Lum]
Lum=" ".join(Lum)
print(Lum)


### FIXED CODE ###

import numpy as np
from numba import jit 
N , K = map(int,input().split())
Lum = np.array(list(map(int,input().split())))

@jit("i8,i8,i8[:]")
def fn(N,K,A):
    K1 = min(K,41)
    for i1 in range(K1):
        B = np.zeros(N,dtype=np.int64)
        for i in range(N):
            l = max(0,i-A[i])
            r = min(N-1,i+A[i])
            B[l]+=1
            if r+1<N:
                B[r+1]-=1
        for i in range(1,N):
            B[i]+=B[i-1]
        A = B
    return A

Lum = list(fn(N,K,Lum))
Lum = [str(l) for l in Lum]
Lum=" ".join(Lum)
print(Lum)
### BUGGY CODE ###

N, M = map(int, input().split())

d = {}
for _ in range(N):
    a, b = map(int, input().split())
    if a in d:
        d[a].append(b)
    else:
        d[a] = [b]

for l in d.values():
    l.sort()


ans = 0
for i in range(1,M+1):
    mx_a = None
    mx_b = 0
    for j in range(1, i+1):
        if j in d and d[j]:
            mx_b = max(mx_b, d[j][-1])
            mx_a = j
    if mx_a is not None:
        ans += mx_b
        d[mx_a].pop(-1)

print(ans)






### FIXED CODE ###

N, M = map(int, input().split())

B = [tuple(map(int, input().split())) for _ in range(N)]
B.sort(reverse=True)

import heapq

hq = []
ans = 0
for i in range(1, M+1):
    while B and B[-1][0] == i:
        heapq.heappush(hq, B.pop()[1]*(-1))
    if hq:
        ans -= heapq.heappop(hq)

print(ans)
### BUGGY CODE ###

def main():
    INF = float('inf')
    H,N = map(int,input().split())
    AB = [list(map(int,input().split())) for _ in range(N)]
    maxA = max(A for A,B in AB)
    dp = [INF]*(H+maxA+1)
    dp[0] = 0
    for i in range(H):
        if dp[i] == INF:
            continue
        else:
            tmp1 = dp[i]
            for j in range(N):
                tmp2 = AB[j][1]
                tmp3 = AB[j][0]
                if tmp1+tmp2 < dp[i+tmp3]:
                    dp[i+tmp3] = tmp1+tmp2
    print(min(dp[H:]))

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    H,N = map(int,input().split())
    AB = [list(map(int,input().split())) for _ in range(N)]
    maxA = max(A for A,B in AB)
    dp = [0]*(H+maxA)
    for i in range(0,H+maxA):
        if i <= 0:
            dp[i] = 0
        else:
            dp[i] = min(dp[i-A]+B for A,B in AB)
    print(min(dp[H:]))


if __name__ == '__main__':
    main()