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

def mul(inp):
    return int(inp * 2)


if __name__ == '__main__':
    n = int(input())
    a = list(map(mul, map(int, input().split())))
    res = [0] * n
    for x in range(0, n):
        res[x] = a[x]
        count = 1
        for i in range(x + 1, n + x):
            mod_i = i % n
            count += 1
            if count % 2 == 0:
                res[x] = res[x] - a[mod_i]
            else:
                res[x] = res[x] + a[mod_i]
        res[x] = str(int(res[x] / 2))
    print(' '.join(res))


### FIXED CODE ###

def mul(inp):
    return int(inp * 2)


if __name__ == '__main__':
    n = int(input())
    a = list(map(mul, map(int, input().split())))
    res = [0] * n
    for x in range(0, 1):
        res[x] = a[x]
        count = 1
        for i in range(x + 1, n + x, 2):
            mod_i = i % n
            res[x] = res[x] - a[mod_i]
        for i in range(x + 2, n + x, 2):
            mod_i = i % n
            res[x] = res[x] + a[mod_i]
        res[x] = int(res[x] / 2)
    for x in range(1, n):
        res[x] = a[x - 1] - res[x - 1]
    print(' '.join(map(str, res)))
### BUGGY CODE ###

N = int(input())
L = sorted(list(map(int, input().split())), reverse=True)

ans = 0
for i in range(N):
    for j in range(i+1, N):
        for k in range(j+1, N):
            a1, a2, a3 = L[i], L[j], L[k]
            if a2+a3 <= a1:
                break
            else:
                ans += 1

print(ans)

### FIXED CODE ###

from bisect import bisect_left, bisect_right  # return index

N = int(input())
L = sorted(list(map(int, input().split())))

ans = 0
for i in range(N):
    for j in range(i+1, N):
        tmp = L[i]+L[j]  # tmpはこの値より短くなくてはいけない

        ### ここから下は二分探索
        ix = bisect_left(L, tmp)
        ans += ix-(j+1)

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

import bisect

N=[int(x)for x in input().split()]
D=[int(x) for x in input().split()]

D.sort(reverse=True)
total=0
# print(D)
def check(a,b,c): #3
    if(a<b+c):
        if(b<a+c):
            if(c<a+b):
                return True
    return False

for i in range(len(D)-1):
    for j in range(i+1,len(D)-1):
        #print("i="+str(i)+" j="+str(j))
        v=D[i]-D[j]
        # print(D[:j:-1])
        # print("v="+str(v))
        # print(len(D[:j:-1]) -bisect.bisect_left(D[:j:-1],v))
        total+=len(D[:j:-1]) - bisect.bisect_left(D[:j:-1],v+0.1)


        # for k in range(j + 1, len(D)):
        #     if(check(D[i],D[j],D[k])):
        #         total+=1
        #         print(str(i)+" "+str(j)+" "+str(k)+"   "+str(total))


print(total)

### FIXED CODE ###

import bisect

N=int(input())
D=[int(x) for x in input().split()]

D.sort()
total=0

for i in range(N-2):
    for j in range(i+1,N-1):
        total+=bisect.bisect_left(D,D[i]+D[j])-j-1

print(total)
### BUGGY CODE ###

import collections
N = int(input())
A = list(map(int,input().split()))
CA = collections.Counter(A)
B = CA.most_common()
S = 0
for i in range(len(B)):
    L = B[i][1]
    if L == 1:
        break
    S += int(L*(L-1)/2)
for k in range(N):
    SS = S - A.count(A[k]) + 1
    print(SS)

### FIXED CODE ###

import collections
N = int(input())
A = list(map(int,input().split()))
CA = collections.Counter(A)
S = 0
for i in CA.values():
    S += i*(i-1)//2
for x in A:
    print(S - CA[x] + 1)
### BUGGY CODE ###

x,y = map(int, input().split())

while True:

    if x == 0 and y == 0 : break

    list = [x, y]
    print(list.sort())
       


### FIXED CODE ###

while True:
    x,y = map(int, input().split())

    if x == 0 and y == 0:
        break

    elif x <= y:
        print(str(x) + " " + str(y))
    else:
        print(str(y) + " " + str(x))
### BUGGY CODE ###

i = 0
x = input()
while x != 0:
 print("Case {}: {}".format(i,x))
 i += i+1



### FIXED CODE ###

i = 1
while True:
 x =int(input())
 if x == 0:
  break
 print("Case {}: {}".format(i,x))
 i = i+1
### BUGGY CODE ###

def comb(n, r): 
    if n<r:
        return 0
    return (fact(n) // (fact(r)  
                * fact(n - r))) 
  
def fact(n):   
    res = 1
    if n<=1:
        return 1
    for i in range(2, n+1): 
        res = res * i
    return res 
  

n = int(input())
a = list(map(int,input().split()))
maxa = max(a)
hasha = [0]*(maxa+1)
for i in a:
    hasha[i]+=1
seta = set(a)
mydict=dict()
sum=0
for i in seta:
    mydict[i] = comb(hasha[i],2)
for i in mydict:
    sum+=mydict[i]
for i in range(n):
    ans = sum + comb(hasha[a[i]]-1, 2) - comb(hasha[a[i]],2)
    print(ans)
    



### FIXED CODE ###

from collections import Counter
n=int(input())
ar=list(map(int,input().split()))
x=Counter(ar)
dct={}
y=list(set(ar))
pair=0
#print(x)
for i in y:
    ct=x[i]-1
    pair+=(ct*(ct+1))//2
#print(pair)
for i in range(n):
    el=ar[i]
    ct=x[el]-1
    add=((ct*(ct+1))//2)-(((ct-1)*((ct-1)+1))//2)
    #print("fff",add)
    print(pair-add)
### BUGGY CODE ###

import numpy as np

def main():
    H, W = map(int, input().split())
    matrix = np.array([np.array(list(input())) for _ in range(H)])
    count_matrix = np.array([np.array([-1 for _ in range(W)]) for _ in range(H)])

    # 横方向についてカウントする
    for i, row in enumerate(matrix):
        start = 0
        count = 0
        for j, s in enumerate(row):
            if s == '.':
                count += 1
                if j == W-1:
                    for k in range(start, j+1):
                        count_matrix[i][k] += count
            else:
                for k in range(start, j):
                    count_matrix[i][k] += count
                start = j+1
                count = 0

    # 縦方向についてカウントする
    for i in range(W):
        column = matrix[:, i]
        start = 0
        count = 0
        for j, s in enumerate(column):
            if s == '.':
                count += 1
                if j == H-1:
                    for k in range(start, j+1):
                        count_matrix[k][i] += count
            else:
                for k in range(start, j):
                    count_matrix[k][i] += count
                start = j+1
                count = 0
    
    print(np.amax(count_matrix))
    return

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    H, W = map(int, input().split())
    matrix = [list(input()) for _ in range(H)]
    L = [[0 for _ in range(W)] for _ in range(H)]
    R = [[0 for _ in range(W)] for _ in range(H)]
    D = [[0 for _ in range(W)] for _ in range(H)]
    U = [[0 for _ in range(W)] for _ in range(H)]

    # 左方向についてカウントする
    for i in range(H):
        if matrix[i][0] == '.':
            L[i][0] = 1
        for j in range(1, W):
            s = matrix[i][j]
            if s == '.':
                L[i][j] = L[i][j-1] + 1

    # 右方向についてカウントする
    for i in range(H):
        if matrix[i][-1] == '.':
            R[i][-1] = 1
        for j in range(W-2, -1, -1):
            s = matrix[i][j]
            if s == '.':
                R[i][j] = R[i][j+1] + 1
    
    # 上方向についてカウントする
    for i in range(W):
        if matrix[0][i] == '.':
            U[0][i] = 1
        for j in range(1, H):
            s = matrix[j][i]
            if s == '.':
                U[j][i] = U[j-1][i] + 1
    
    # 下方向についてカウントする
    for i in range(W):
        if matrix[-1][i] == '.':
            D[-1][i] = 1
        for j in range(H-2, -1, -1):
            s = matrix[j][i]
            if s == '.':
                D[j][i] = D[j+1][i] + 1    
    
    max_val = -3
    for i in range(H):
        for j in range(W):
            max_val = max(max_val, R[i][j]+L[i][j]+U[i][j]+D[i][j])
    print(max_val-3)
    return

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

def hantei(n,data):
    last_num = 1
    if last_num not in data:
        return -1

    while True:
        data = data[data.index(last_num):]
        if last_num + 1 in data:
            last_num += 1
        else:
            break
        #print(data[index_point + 1:])

    return n - last_num

n = int(input())
data = [int(x) for x in input().split()]

print(hantei(n,data))

### FIXED CODE ###

def hantei(n,data):
    v = 1

    for st in data:
        if st == v:
            v = v + 1

    if v == 1:
        return -1
    else:
        return n - v + 1

n = int(input())
data = [int(x) for x in input().split()]

print(hantei(n,data))
### BUGGY CODE ###

# this is a good problem !

import sys
si = sys.stdin.readline

d = ['R', 'G', 'B']
ld = [[0], [0], [0]]  # letter distribution


def main():
    count = 0
    n = int(si())
    s = si()[:-1]
    dc = d[:]

    for i in range(n-1, -1, -1):
        for j in range(3):
            if s[i] == dc[j]:
                ld[j] = [1+ld[j][0]]+ld[j]
            else:
                ld[j] = [ld[j][0]]+ld[j]

    for i in range(n-2):
        rgb1 = s[i]
        dc.remove(rgb1)
        for j in range(i+1, n-1):
            if s[j] in dc:
                rgb2 = s[j]
                dc.remove(rgb2)
                count += ld[d.index(dc[0])][j+1]
                k = j+j-i
                if k < n and s[k] in dc:
                    count -= 1
                dc += [rgb2]
        dc += [rgb1]
    print(count)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
si = sys.stdin.readline
so = sys.stdout.write


def main():
    n = int(si())
    s = si()[:-1]
    cnt = s.count('R')*s.count('G')*s.count('B')

    for i in range(n-2):
        for j in range(i+1, n-1):
            k = j+j-i
            if k < n and s[i] != s[j] and s[j] != s[k] and s[k] != s[i]:
                cnt -= 1

    print(cnt)


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

X,Y,Z,K = map(int,input().split())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
C=list(map(int,input().split()))
XY=[]
A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)
for a in A[:K]:
    for b in B[:K]:
        XY.append(a+b)
XY.sort(reverse=True)
XY=XY[:K]
XYZ=[]
for xy in XY:
    for c in C:
        XYZ.append(xy+c)
XYZ.sort(reverse=True)
for i in range(K):
    print(XYZ[i])


### FIXED CODE ###

X,Y,Z,K = map(int,input().split())
A = sorted(list(map(int, input().split())), reverse=True)
B = sorted(list(map(int, input().split())), reverse=True)
C = sorted(list(map(int, input().split())), reverse=True)
xy=[]
for a in A:
    for b in B:
        xy.append(a+b)
xy=sorted(xy,reverse=True)
xy=xy[:K]
xyz=[]
for c in C:
    for x in xy:
        xyz.append(x+c)
xyz=sorted(xyz,reverse=True)
for i in range(K):
    print(xyz[i])
### BUGGY CODE ###

N = int(input())

n = N
memo = []
cnt = 0
while N > 1:
    for i in range(2,N+1):
        if i in memo:
            continue
        if N % i == 0:
            memo.append(i)
            n = N // i
            cnt += 1
        N = n    
print(cnt)        

### FIXED CODE ###

from functools import reduce
from bisect import bisect

def soinsuu_bunkai(n):
    ret = {}
    p = 2
    while p * p <= n:
        while n % p == 0:
            ret[p]= ret[p]+1 if p in ret else 1
            n //= p
        p += 1
    if n != 1:
        ret[n] = 1
    return ret   
    
def make_triangle(n):
    cnt = 0
    sum_ = 0
    for i in range(1,n+1):
        sum_ += i
        if sum_ > n:
            break
        else:
            cnt += 1
    return cnt    

dic = soinsuu_bunkai(int(input()))
ans = 0
for k,v in dic.items():
    ans += make_triangle(v)  
print(ans)
### BUGGY CODE ###

MOD = 10**9+7
N,M = map(int,input().split())
a = [int(input()) for _ in range(M)]
x = 0
y = 1
for i in range(N):
  if (i+1 in a) and (i in a):
    print(0)
    exit()
  elif i+1 in a:
    z = 0
  else:
    z = x + y
  x = y
  y = z
print(z%MOD)


### FIXED CODE ###

import bisect
def f(x,a):
  global M
  b = bisect.bisect_left(a,x)
  if x==a[min(b,M)]:
    return True
  else:
    return False
MOD = 10**9+7
N,M = map(int,input().split())
a = [-1]+[int(input()) for _ in range(M)]
a.sort()
x = 0
y = 1
for i in range(N):
  if f(i,a) and f(i+1,a):
    print(0)
    exit()
  elif f(i+1,a):
    z = 0
  else:
    z = x + y
  x = y
  y = z
print(z%MOD)
### BUGGY CODE ###

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

arr = [0] * (N)
tmp = 0

for i in range(N):
  n = P[i]
  arr[i] = (n*(n+1)/2)/n

for i in range(0, N - K + 1):
  max_value = 0
  for j in range(K):
    max_value += arr[i+j]
  if max_value >= tmp:
    tmp = max_value

print(tmp)


### FIXED CODE ###

import queue

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

q = queue.Queue()

#arr = [(n+1)/2 for n in P]
mx = 0
s = 0

for i in range(N):
  s += P[i]+1
  q.put(P[i]+1)
  if q.qsize() > K:
    s -= q.get()
  if q.qsize() == K:
    mx = max(mx, s)

ans = mx/2
print(ans)
### BUGGY CODE ###

k,s=map(int,input().split())
ans=0
for x in range (k+1):
    for y in range (k+1):
        for z in range (k+1):
            if x+y+z==s:
                ans=ans+1
print(ans)

### FIXED CODE ###

k,s=map(int,input().split())
ans=0
for x in range (k+1):
    for y in range (k+1):
        z=s-x-y
        if 0<=z<=k:
            ans=ans+1
print(ans)
### BUGGY CODE ###

from sys import stdin, setrecursionlimit
from bisect import bisect_left

setrecursionlimit(10 ** 9)
INF = 1 << 60


def input():
    return stdin.readline().strip()


def main():
    N = int(input())
    A = tuple(int(input()) for _ in range(N))
    B = [A[0]]

    for a in A[1:]:
        if a <= B[0]:
            B.insert(0, a)
        else:
            B[bisect_left(B, a) - 1] = a

    print(len(B))


if __name__ == '__main__':
    main()


### FIXED CODE ###

from sys import stdin, setrecursionlimit
from bisect import bisect_left
from collections import deque

setrecursionlimit(10 ** 9)
INF = 1 << 60


def input():
    return stdin.readline().strip()


def main():
    N = int(input())
    A = tuple(int(input()) for _ in range(N))
    B =deque([A[0]])

    for a in A[1:]:
        if a <= B[0]:
            B.appendleft(a)
        else:
            B[bisect_left(B, a) - 1] = a

    print(len(B))


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

a = [int(input()) for _ in range(int(input()))]
print(sum([1 for i in set(a) if a.count(i) % 2 == 1]))

### FIXED CODE ###

A = {}
for _ in range(int(input())):
    a = input()
    A[a] = A.get(a, 0) + 1

print(len(list(filter(lambda x: x % 2 != 0, A.values()))))
### BUGGY CODE ###

N = int(input())
x = [None]*N
y = [None]*N
h = [None]*N

for i in range(N):
    x[i],y[i],h[i] = map(int, input().split())

def height(X,Y,xn,yn,hn):
    return hn+abs(X-xn)+abs(Y-yn)

def check(x,y,h,X,Y,H):
    for n in range(N):
        if h[n]>0:
            if height(X,Y,x[n],y[n],h[n])!=H:
                return False
        elif H-abs(X-x[n])-abs(Y-y[n])>0:
            return False
    return True

for X in range(101):
    for Y in range(101):
        for n in range(N):
            H = height(X,Y,x[n],y[n],h[n])
            if check(x,y,h,X,Y,H) is True:
                print(X,Y,H)
                exit()


### FIXED CODE ###

N = int(input())
x = [None]*N
y = [None]*N
h = [None]*N

for i in range(N):
    x[i],y[i],h[i] = map(int, input().split())

def height(X,Y,xn,yn,hn):
    return hn+abs(X-xn)+abs(Y-yn)

def check(x,y,h,X,Y,H):
    for n in range(N):
        if h[n]>0:
            if height(X,Y,x[n],y[n],h[n])!=H:
                return False
        elif H-abs(X-x[n])-abs(Y-y[n])>0:
            return False
    return True

for X in range(101):
    for Y in range(101):
        for n in range(N):
            if h[n]>0:
                H = height(X,Y,x[n],y[n],h[n])
                if check(x,y,h,X,Y,H) is True:
                    print(X,Y,H)
                    exit()
### BUGGY CODE ###

s = input()
q = int(input())
top = ""
end = ""
count = 0
for i in range(q):
    a = list(input().split())
    if len(a) == 1:
        count += 1
    else:
        if (count + int(a[1])) % 2 == 0:
            end = end + a[2]
        else:
            top = a[2] + top
ans = top + s + end
if count % 2 == 1:
    ans = ans[::-1]
print(ans)

### FIXED CODE ###

s = input()
q = int(input())
top = ""
end = ""
count = 0
for i in range(q):
    a = input()
    if len(a) == 1:
        count += 1
    else:
        a = list(a.split())
        if (count + int(a[1])) % 2 == 0:
            end = end + a[2]
        else:
            top = a[2] + top
ans = top + s + end
if count % 2 == 1:
    ans = ans[::-1]
print(ans)
### BUGGY CODE ###

import sys
import cProfile
input = sys.stdin.readline
def main():
    n=int(input())
    a=[int(input()) for _ in range(n)]
    l=[1]
    i=0
    aa=1
    while True:
        aa=a[aa-1]
        if aa == 2:
            print(i+1)
            sys.exit()
        if aa in l:
            print(-1)
            sys.exit()
        l.append(aa)
        i+=1
main()

### FIXED CODE ###

import sys
import cProfile
input = sys.stdin.readline
def main():
    n=int(input())
    a=[int(input()) for _ in range(n)]
    l=[1]
    i=0
    aa=1
    while True:
        aa=a[aa-1]
        if aa == 2:
            print(i+1)
            sys.exit()
        if i>n:
            print(-1)
            sys.exit()
        i+=1
main()
### BUGGY CODE ###

# from math import factorial,sqrt
# from itertools import permutations as permus
# from fractions import gcd
from collections import deque,Counter
# from decimal import Decimal, getcontext
# # getcontext().prec = 1000
# # eps = Decimal(10) ** (-100)

# import numpy as np
# import scipy as scp

# 入力の受け取り
n = int(input())
arrA = list(map(int,input().split()))

ctA = Counter(arrA)
dp = {}
cbdp = {}
for i in arrA:
    if i in dp:
        print(dp[i])
        continue
    ctA[i] -= 1
    temp = 0
    for k,v in ctA.items():
        if v<=1:
            continue
        elif v in cbdp:
            temp += cbdp[v]
        else:
            temp += v*(v-1)//2
            cbdp[v] = v*(v-1)//2
    print(temp)
    dp[i] = temp
    ctA[i] += 1

# print(*ans,sep="\n")
# print("{:.10f}".format(ans))
# print(*ans)   # unpackして出力。間にスペースが入る
# for row in board:
#     print(*row,sep="")    #unpackして間にスペース入れずに出力する



### FIXED CODE ###

# from math import factorial,sqrt
# from itertools import permutations as permus
# from fractions import gcd
from collections import deque,Counter
# from decimal import Decimal, getcontext
# # getcontext().prec = 1000
# # eps = Decimal(10) ** (-100)

# import numpy as np
# import scipy as scp

# 入力の受け取り
n = int(input())
arrA = list(map(int,input().split()))

cbdp = [0,0]
cbdp2 = [i*(i-1)//2 for i in range(2,n+1)]
cbdp += cbdp2
# print(cbdp)

ctA = Counter(arrA)
# print(ctA)

totalconb = 0
for v in ctA.values():
    totalconb += cbdp[v]
# print(totalconb)

for a in arrA:
    print(totalconb-cbdp[ctA[a]]+cbdp[ctA[a]-1])

# print(*ans,sep="\n")
# print("{:.10f}".format(ans))
# print(*ans)   # unpackして出力。間にスペースが入る
# for row in board:
#     print(*row,sep="")    #unpackして間にスペース入れずに出力する
### BUGGY CODE ###

n = int(input())
S = input().split()
q = int(input())
T = input().split()

count = 0
for i in T:
        if i in S:
            count += 1

print(count)

### FIXED CODE ###

n = int(input())
S = set(int(i) for i in input().split())
q = int(input())
T = set(int(i) for i in input().split())
print(len(S & T))
### BUGGY CODE ###

import sys, copy

def gcd(x, y):
	if y == 0:
		return x
	else:
		return gcd(y, x % y) #再帰定義

def listgcd(A):
	newA = []
	if len(A) % 2 == 1:
		A.append(0)
	
	for i in range(0, len(A), 2):
		newA.append(gcd(A[i], A[i + 1]))
	
	if len(newA) == 1:
		return newA[0]
	else:
		return listgcd(newA)
	
input = sys.stdin.readline
'''
allinputs = iter(input().splitlines())
input = lambda : next(allinputs)
#'''

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

ans = 0

for i in range(N):
	B = copy.copy(A)
	B[i] = 0
	tmp = listgcd(B)
	if ans < tmp:
		ans = tmp
		
print(ans)


### FIXED CODE ###

import sys

def gcd(x, y):
	if y == 0:
		return x
	else:
		return gcd(y, x % y) #再帰定義
	
input = sys.stdin.readline
'''
allinputs = iter(input().splitlines())
input = lambda : next(allinputs)
#'''

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

L = [0] * N
R = [0] * N
ans = 0
L[0] = 0
R[0] = 0

for i in range(1, N):
	L[i] = gcd(L[i - 1], A[i - 1])
	R[i] = gcd(R[i - 1], A[N - i])

for i in range(N):
	tmp = gcd(L[i], R[N - 1 - i])
	if tmp > ans:
		ans = tmp
		
print(ans)
### BUGGY CODE ###

list1=list(input())
count=0
fin=0
while fin==0 and len(list1)>1:
    for i in range(len(list1)-1):
        if list1[i]=="B" and list1[i+1]=="W":
            count+=1
            list1[i]="W"
            list1[i+1]="B"
            break
        if i==len(list1)-2:
            fin=1
print(count)

### FIXED CODE ###

list1=list(input())
list1.reverse()
a=0
count=0
for i in range(len(list1)):
    if list1[i]=="W":
        a=i
        break
for i in range(a,len(list1)):
    if list1[i]=="B":
        count+=i-a
        a+=1
print(count)
### BUGGY CODE ###

# D Knapsack 1
import copy

n, w = map(int, input().split())
wv_list = [[int(x) for x in input().split()] for y in range(n)] # n*2

dp = [float('-Inf')] * (w+2)
dp[0] = 0
buy_list = [[False] * n for j in range(w+2)] # (w+2)*n

for i in range(w):
    for j in range(n):
        if buy_list[i][j]:
            continue
        _w = wv_list[j][0]
        _v = wv_list[j][1]
        if i+_w > w:
            _w = w - i + 1
        if dp[i+_w] < dp[i]+_v:
            dp[i+_w] = dp[i]+_v
            buy_list[i+_w] = copy.deepcopy(buy_list[i])
            buy_list[i+_w][j] = True
            
print(max(dp[:w+1]))

### FIXED CODE ###

# D Knapsack 1

from collections import deque

n, w = map(int,input().split())
wv_list = deque([[int(x) for x in input().split()] for y in range(n)])

dp = [[float("-Inf")] * (w+1) for _ in range(n+1)]
dp[0] = [0]*(w+1)

for i in range(n):
    _w,_v = wv_list.popleft()
    for j in range(w+1):
        if j-_w < 0:
            dp[i+1][j] = dp[i][j]
        else:
            dp[i+1][j] = max(dp[i][j], dp[i][j-_w]+_v)

print(dp[n][w])
### BUGGY CODE ###

from collections import deque
import sys
input=sys.stdin.readline
n,m=map(int,input().split())
a=deque(sorted(list(map(int,input().split()))))
x=[]
for i in range(m):x.append(list(map(int,input().split()))[::-1])
x.sort(reverse=1)
s=0
for i,j in x:
  for k in range(j):
    if i<a[0]:s=1;break
    aa=a.popleft();a.append(i)
  if s==1:break
print(sum(a))

### FIXED CODE ###

from collections import deque
import sys
input=sys.stdin.readline
n,m=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
a=deque(a)
x=[]
for i in range(m):x.append(list(map(int,input().split()))[::-1])
x.sort(reverse=1)
for i,j in x:
  for k in range(j):
    if i<=a[0]:print(sum(a));exit()
    a.popleft();a.append(i)
print(sum(a))
### BUGGY CODE ###

from sys import stdin
input = stdin.readline


def main():
  H, N = list(map(int, input().split()))
  A = [0]*N
  B = [0]*N
  for i in range(N):
    A[i], B[i] = map(int, input().split())

  dp = [[0]*(H+1) for _ in range(N+1)]
  for j in range(H+1):
    dp[0][j] = float('inf')
  dp[0][0] = 0

  for i in range(1, N+1):
    for j in range(1, H+1):
      dp[i][j] = dp[i-1][j]
      if j > A[i-1]:
        dp[i][j] = min(dp[i][j], dp[i][j-A[i-1]]+B[i-1])
      else:
        dp[i][j] = min(dp[i][j], B[i-1])

  # for i in range(N+1):
  #   print(dp[i])
  print(dp[N][H])


if(__name__ == '__main__'):
  main()

### FIXED CODE ###

from sys import stdin
input = stdin.readline


def main():
  H, N = list(map(int, input().split()))
  A = [0]*N
  B = [0]*N
  for i in range(N):
    A[i], B[i] = map(int, input().split())

  # dp = [[0]*(H+1) for _ in range(N+1)]
  dp = [0]*(H+1)
  for j in range(H+1):
    dp[j] = float('inf')
  dp[0] = 0

  for i in range(1, N+1):
    for j in range(1, H+1):
      # dp[i][j] = dp[i-1][j]
      if j > A[i-1]:
        dp[j] = min(dp[j], dp[j-A[i-1]]+B[i-1])
      else:
        dp[j] = min(dp[j], B[i-1])

  # for i in range(N+1):
  #   print(dp[i])
  print(dp[H])


if(__name__ == '__main__'):
  main()