Harryxun/stf_run huggingface dataset:
md = 1000000007
dp=[]
def countways(n,broken,ix):
	global dp,md
	if(dp[ix]!=-1):
		return dp[ix]

	ways = 0
	if((ix+1)<=n and broken[ix+1]==0):
		ways+=countways(n,broken,ix+1)
	if((ix+2)<=n and broken[ix+2]==0):
		ways+=countways(n,broken,ix+2)
	dp[ix]=(ways%md)
	return dp[ix]

n,m = list(map(int,input().split()))
dp = [-1 for i in range(n+1)]
dp[n] = 1
broken = [0 for i in range(n+1)]
for i in range(m):
	broken[int(input())]=1
# print(brok	en)
print(countways(n,broken,0)%md)

### FIXED CODE ###

md = 1000000007
n,m = list(map(int,input().split()))
broken = [0 for i in range(n+1)]
dp=[0 for i in range(n+1)]
dp[0] = 1
for i in range(m):
	broken[int(input())]=1
# print(brok	en)
for j in range(1,n+1):
	if(broken[n-j]==1):
		continue
	if(j==1):
		dp[j]=1
	else:
		dp[j]=(dp[j-1]+dp[j-2])%md
# print(dp)
print(dp[n]%md)
S = input()
N = len(S)

def is_circular(string):
    reverse = string[::-1]
    if string == reverse:
        return True
    else:
        return False

if is_circular(S) and is_circular(S[:(N)//2]) and is_circular(S[(N+3)//2]):
    print('Yes')
else:
    print('No')

### FIXED CODE ###

S = input()
N = len(S)

if N == 3:
    if S[0] == S[2]:
        print('Yes')
    else:
        print('No')
    exit()

def is_circular(string):
    reverse = string[::-1]
    if string == reverse:
        return True
    else:
        return False

if is_circular(S) and is_circular(S[:(N)//2]) and is_circular(S[(N+3)//2]):
    print('Yes')
else:
    print('No')
data = [int(i) for i in input().split()]

data.sort()
print("{0}{1}{2}".format[data[0],data[1],data[2]])

### FIXED CODE ###

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

data.sort()
print("{0} {1} {2}".format(data[0],data[1],data[2]))
n = int(input())
p = [int(input()) for _ in range(n)]

q = [0] * (n+1)
for i in range(n):
    q[p[i]] = q[p[i]-1] + 1

print(q - max(q))


### FIXED CODE ###

n = int(input())
p = [int(input()) for _ in range(n)]

q = [0] * (n+1)
for i in range(n):
    q[p[i]] = q[p[i]-1] + 1

print(n - max(q))
n = int(input())
d, x = map(int,input().split())
res = x

for i in range(n):
    a = int(input())
    if a == 1:
        res +=d
    else :
        res += (d-1)//a + 1
print(res)

### FIXED CODE ###

a=int(input())
b=int(input())
c=int(input())
d=int(input())
print(min(a,b)+min(c,d))
N, K = list(map(int, input().strip().split()))
A = list(map(int, input().strip().split()))

import numpy as np

Base = np.prod(A[:K])
for n in range(N-K):
  Tgt_i = np.prod(A[n:K+n])
  Tgt_i1 = np.prod(A[n+1:K+n+1])
  if Tgt_i < Tgt_i1:
    print('Yes')
  else:
    print('No')

### FIXED CODE ###

N = int(input().strip())

if N<=599:print(8)
elif N<=799:print(7)
elif N<=999:print(6)
elif N<=1199:print(5)
elif N<=1399:print(4)
elif N<=1599:print(3)
elif N<=1799:print(2)
else: print(1)
s = [*input()]
ans = 1000
for i in range(len(s) - 2):
  x = int(s[i] + s[i+1] + s[i+2])
  if ans > abs(753 - x):
    ans = abs(753 - x)
print(ans)

### FIXED CODE ###

s = [s for s in input()]
ans = 1000
for i in range(len(s)-2):
    x = int(s[i]+s[i+1]+s[i+2])
    if ans > abs(753-x):
        ans = abs(753-x)
print(ans)
num = int(input())
ac = 0
wa = 0
tle = 0
re = 0
for i in range(num):
    word = input()
    if word == "AC":
        ac = ac + 1
    elif word == "WA":
        wa = wa + 1
    elif word == "TLE":
        tle = tle + 1
    elif word == "RE":
        re = re + 1
print("AC x ",ac)
print("WA x ",wa)
print("TLE x ",tle)
print("RE x ",re)


### FIXED CODE ###

yen = 1000-(int(input())%1000)
if yen == 1000:
    print(0)
else:
    print(yen)
n,m=map(int,input().split())

s=[0]*n

for _ in range(m):
  s[int(input())-1]=""
  
#print(s)

if n==1:
  print(1)
  exit()
elif n==2:
  if s[0]=="":
    print(1)
  else:
    print(2)
  exit()
  
if s[0]=="":
  s[0]=0
else:
  s[0]=1
  
if s[1]=="":
  s[1]=0
else:
  s[1]=1+s[0]

i=2
while i<n:
  if s[i]=="":
    s[i]=0
  else:
    s[i]=s[i-1]+s[i-2]
  i+=1
print(s[-1]%1000000007)

### FIXED CODE ###

n=int(input())
r=list(map(int,input().split()))

s=abs(sum(r[:1])-sum(r[1:]))

for i in range(1,n):
  s=min(s,abs(sum(r[:i])-sum(r[i:])))
        
print(s)
import copy

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

t = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
L = {}
for i in A:
  if t[i] in L:
    if L[t[i]] < i:
      L[t[i]] = i
  else:
    L[t[i]] = i
  
dp = [[0 for j in range(10)] for i in range(N)]
ja = [0 for j in range(10)]
for i in L.items():
  dp[i[0] - 1][i[1]] = 1
for i in range(N):
  if dp[i] == ja:
    continue
  for j in L.items():
    k = i + j[0]
    if k < N:
      t = copy.deepcopy(dp[i])
      t[j[1]] += 1
      for ii in range(9, 0, -1):
        if t[ii] > dp[k][ii]:
          dp[k] = t
          break
        elif t[ii] < dp[k][ii]:
          break
          
t = dp[-1]
Ans = ""
for i in range(9, 0, -1):
  for k in range(t[i]):
    Ans += str(i)
    
print(Ans)

### FIXED CODE ###

import copy

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

t = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
L = {}
for i in A:
  if t[i] in L:
    if L[t[i]] < i:
      L[t[i]] = i
  else:
    L[t[i]] = i

dp = [[0 for j in range(10)] for i in range(N)]
for i in L.items():
  if i[0] - 1 < N:
    dp[i[0] - 1][i[1]] = 1
for i in range(N):
  if max(dp[i]) == 0:
    continue
  for j in L.items():
    k = i + j[0]
    if k < N:
      t = copy.deepcopy(dp[i])
      t[j[1]] += 1
      if sum(t) > sum(dp[k]):
        dp[k] = t
      else:
        for ii in range(9, 0, -1):
          if t[ii] > dp[k][ii]:
            dp[k] = t
            break
          elif t[ii] < dp[k][ii]:
            break
          
t = dp[-1]
Ans = ""
for i in range(9, 0, -1):
  for j in range(t[i]):
    Ans += str(i)
    
print(Ans)
import NumPy as np
n, m = map(int, raw_input().split())
a = np.array(map(int, raw_input().split()))
for i in xrange(n-1):
	a = np.c_[a, (map(int, raw_input().split()))]
b = np.array(map(int, raw_input().split()))
for i in xrange(m-1):
	b = np.r_[b, (map(int, raw_input().split()))]
for i in xrange(n):
	print b.dot(a)[i]

### FIXED CODE ###

n, m = map(int, raw_input().split())
 
a = [[0]*m for i in xrange(n)]
 
b = [0]*m
 
for i in xrange(n):
    tmp = map(int, raw_input().split())
    for j in xrange(m):
        a[i][j] = tmp[j]
for i in xrange(m):
    b[i] = input()
for i in xrange(n):
    tmp = 0
    for j in xrange(m):
        tmp += a[i][j] * b[j]
    print tmp
def gcd(a,b):
  if a<=b:
    return gcd(b,a)
  elif a%b==0:
    return b
  else:
    return gcd(b,a%b)
N=int(input())
A=list(map(int,input().split()))
ans=A[0]
for a in A:
  ans=gcd(ans,a)
print(ans)

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
a=min(A)
S={n%a for n in A if n%a!=0}

while len(S)>0:
    tmp=a
    a=min(S)
    S={n%a for n in S if n%a!=0}
    if tmp%a!=0:
        S.add(tmp%a)
print(a)
D = int(input())

if D = 25:
  print('Christmas')
  
if D = 24:
  print('Christmas Eve')
  
if D = 23:
  print('Christmas Eve Eve')
  
if D = 22:
  print('Christmas Eve Eve Eve')

### FIXED CODE ###

D = int(input())

if D == 25:
  print('Christmas')
  
if D == 24:
  print('Christmas Eve')
  
if D == 23:
  print('Christmas Eve Eve')
  
if D == 22:
  print('Christmas Eve Eve Eve')
N, K = map(int, input().split())
A = list(map(int, input().split()))
ans = 0
 
assert K > 5
 
print(114514)

### FIXED CODE ###

input_line = input().split()

num_array = int(input_line[0])
num_equal = int(input_line[1])

input_line = input() # 無視

equalized = 1
i = 0
while equalized < num_array:
    equalized += (num_equal - 1)
    # print(i, equalized)
    i += 1

print(str(i))
num = list(map(input().split()))
word = [input() for i in range(num[0])]
print(''.join(sorted(word)))

### FIXED CODE ###

n = list(map(int,input().split()))
word = [input() for i in range(n[0])]
print(''.join(sorted(word)))
MOD = int(10**9+7)
n = int(input())
a = list(map(int, input().split()))
a = sorted(a)

if n%2 == 0:
    a_valid = []
    for i in range(1, n, 2):
        a_valid += [i, i]
    if a == a_valid:
        print(int((2**(n/2))%MOD))
    else:
        print(0)
else:
    a_valid = [0]
    for i in range(2, n, 2):
        a_valid += [i, i]
    if a == a_valid:
        print(int((2**int(n/2))%MOD))
    else:
        print(0)        


### FIXED CODE ###

MOD = 10**9+7
n = int(input())
a = list(map(int, input().split()))
a = sorted(a)

if n%2 == 0:
    valid = True
    for i in range(n):
        if i%2 == 0: v = i+1
        else: v = i
        if a[i] != v:
            valid = False
            print(0)
            break
    if valid:
        print(2**(n//2)%MOD)

else:
    valid = True
    for i in range(n):
        if i%2 != 0: v = i+1
        else: v = i
        if a[i] != v:
            valid = False
            print(0)
            break
    if valid:
        print(2**(n//2)%MOD)
import sys
input = sys.stdin.readline
from itertools import combinations

N = int(input().rstrip())
s = [int(input().rstrip()) for _ in range(N)]
s.sort(reverse=1)

for s in s:
    if s % 10 != 0:
        break
else:
    print(0)

for i in range(N, 0, -1):
    for c in combinations(s, i):
        if sum(c) % 10 == 0:
            continue
        else:
            print(sum(c))
            exit()

### FIXED CODE ###

import sys
input = sys.stdin.readline
from itertools import combinations

N = int(input().rstrip())
score = [int(input().rstrip()) for _ in range(N)]
score.sort(reverse=1)

s_multiple_of_10 = [s for s in score if s % 10 == 0]
if len(s_multiple_of_10) == N: print(0)
s_not_multiple_of_10 = [s for s in score if s % 10 != 0]

# combinationsでも、先に１０の倍数を除外してから処理したらどうだろう
for i in range(len(s_not_multiple_of_10), 0, -1):
    for c in combinations(s_not_multiple_of_10, i):
        if sum(c) % 10 == 0:
            continue
        else:
            print(sum(c) + sum(s_multiple_of_10))
            exit()
import math
a = input()
if a[-4] != '0':
  b = int(a[-5:])
elif a[-3] != '0':
  b = int(a[-4:])
elif a[-2] != '0':
  b = int(a[-3:])
else:
  b = int(a[-0])
c = 1000
print(c-b)

### FIXED CODE ###

import math
a = input()
b = int(a)
c = 1000
if len(a) < 4:
  print(c-b)
else:
  if a[-4] != '0':
    b = int(a[-3:])
    if b == 0:
      print(int(0))
    else:
      print(c-b)
  elif a[-3] != '0':
    b = int(a[-2:])
    print(c-b)
  elif a[-2] != '0':
    b = int(a[-1:])
    print(c-b)
  else:
    print(int(0))
a = input()
b = int(a)
c = list(a)
t = int(a[0])
print(t,a.count("9"))
if t != 9  and a.count("9") == len(a)-1:
    r = t+(len(a)-1)*9
elif a.count("9") != len(a):
    t -= 1
    r = t+(len(a)-1)*9
if b<9:
    r = b
    
print(r)

### FIXED CODE ###

a = input()
b = int(a)
c = list(a)
t = int(a[0])
r = t+(len(a)-1)*9
#print(t,a.count("9"))
if t != 9  and a.count("9") == len(a)-1:
    r = t+(len(a)-1)*9
elif a.count("9") != len(a):
    t -= 1
    r = t+(len(a)-1)*9
if b<9:
    r = b
elif b == 9:
    r = 9
    
print(r)
# -*- coding: utf-8 -*-

def conbination(n, r):
    return f[n] // f[r]*f[n-r]

f = [1]
for i in (1, 2001)
    f.append(int(f[i-1]*i))

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

for i in range(1, K+1):
    c_blue = conbination(K-1, i-1)
    c_red = conbination(N-K+1, i)
    print((c_blue * c_red) % (10**9 + 7))


### FIXED CODE ###

# -*- coding: utf-8 -*-

def conbination(n, r):
    return f[n] // (f[r] * f[n-r])

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

f = [1]
for i in range(1, N+1):
    f.append(int(f[i-1]*i))

for i in range(1, K+1):
    if i > N-K+1:
        print(0)
        continue
    c_blue = conbination(K-1, i-1)
    c_red = conbination(N-K+1, i)
    print((c_blue * c_red) % (10**9 + 7))
a,b = map(int,input().sprit())
if a >= 13:
  print(b)
elif 6 <= a <= 12:
  print(b//2)
else:
  print(0)

### FIXED CODE ###

a,b = map(int,input().split())
if a >= 13:
  print(b)
elif 6 <= a <= 12:
  print(b//2)
else:
  print(0)
n, k=map(int, input().split())

ans=(k-1)**(n-1)

print(ans*k)

### FIXED CODE ###


def penki(a, b, c):
  if a==b and b==c:
    return 1
  elif a!=b and b!=c and c!=a:
    return 3
  else:
    return 2

a,b,c=map(int, input().split())
print(penki(a, b, c))
def main():
    import math
    from functools import reduce

    n, x, *l = map(int, open(0).read().split())
    a = list(map(lambda i: abs(i-x), l))
    ans = reduce(math.gcd, a)
    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    import fractions
    from functools import reduce

    n, x, *l = map(int, open(0).read().split())
    a = list(map(lambda i: abs(i-x), l))
    ans = reduce(fractions.gcd, a)
    print(ans)


if __name__ == '__main__':
    main()
def solve():
    n=int(input())
    a=[int(input()) for _ in range(n)]
    num1=max(a)
    count=0
    while count!=n:
        if a[count]==num1:
            if count==0:
                print(max(a[1:]))
            elif count==n-1:
                print(max(a[:n-1]))
            else:
                print(max(max(a[:count]),max(a[count+1:])))
        else:
            print(num1)
        count+=1
solve()


### FIXED CODE ###

r=int(input())
print(3*r*r)
import sys
import math
import itertools

a, b = map(int, input().split())
print(int(a * b / math.gcd(a, b)))

### FIXED CODE ###

import sys
from math import ceil, floor, sqrt, sin, cos, pi
from itertools import accumulate, permutations, combinations
from fractions import gcd
from collections import deque, Counter
from operator import itemgetter
from heapq import heappop,heappush
sys.setrecursionlimit(10**7)

a, b = map(int, input().split())
print(int(a * b / gcd(a, b)))
import math
 
money=int(N)
if money%1000==0:
  print(0)
else:
  money=(math.ceil(money/1000))*1000-money
  print(money)

### FIXED CODE ###

n = int(input())

if n % 1000 == 0:
  print(0)
else:
  print(1000-(n%1000))
ist(map(int,input().split()))

ans = 0
for i in range(N):
    ans ^= A[i]

for i in range(N):
    A[i] = (~ans)&A[i]
    A[i] *= -1

A = [a for a in A if a != 0]
heapq.heapify(A)
b = []

if A:
    M = -heapq.heappop(A)
    while A:
        m = -heapq.heappop(A)
        if len(bin(M)) == len(bin(m)):
            m ^= M
            if m != 0:
                heapq.heappush(A,-m)
        else:
            b.append(M)
            M = m
    b.append(M)

    b = b[::-1]
    ans_ = 0
    for i in range(len(b)):
        M = b[i]
        for j in range(i+1,len(b)):
            m = b[j]
            if len(bin(M))==len(bin(M&m)):
                b[j] ^= M
        ans_ ^= M

    ans += ans_*2
print(ans)


### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
ans = 0
for a in A:
    ans ^= a
M = 2**60-1
b = M^ans
for i in range(N):
    A[i] &= b
A.sort(reverse=True)
for i in range(min(60,N)):
    a = A[i]
    if a == 0:
        break
    l = len(bin(a))-3
    for j in range(N):
        if j==i:
            continue
        if A[j]//2**l%2==1:
            A[j] ^= a
        else:
            if i < j:
                break
    A.sort(reverse=True)
s = 0
for a in A:
    s ^= a
ans += 2*s
print(ans)
print(Yes)

### FIXED CODE ###

n,a,b,c,d = [int(i) for i in input().split()]
s = input()


flag1 = False
block = 0
for i in range(b, len(s)):
    if block == 2:
        flag1 = False
        break
    elif i == d-1:
        flag1 = True
        break
    elif s[i] == ".":
        block = 0
    elif s[i] == "#":
        block += 1

if flag1 == True:
    s2 = s[:d-1]+'#'+s[d:]
    flag1 = False
    block = 0
    for i in range(a, len(s)):
        if block == 2:
            flag1 = False
            break
        elif i == c-1:
            flag1 = True
            break
        elif s2[i] == ".":
            block = 0
        elif s2[i] == "#":
            block += 1


flag2 = False
flag3 = False
temp = 0
block = 0
for i in range(b-2,c-2):
    if temp == 3:
        flag2 = True
        temp = i-1
        break
    elif s[i] == "#":
        temp = 0
    elif s[i] == ".":
        temp += 1

if flag2 == True:
    flag3 = False
    block = 0
    s1 = s[:temp-1]+'#'+s[temp:]
    for i in range(a, len(s)):
        if block == 2:
            flag3 = False
            break
        elif i == c-1:
            flag3 = True
            break
        elif s1[i] == ".":
            block = 0
        elif s1[i] == "#":
            block += 1

    if flag3 == True:
        s3 = s1[:c - 1] + '#' + s1[c:]
        flag3 = False
        block = 0
        for i in range(temp, len(s)):
            if block == 2:
                flag3 = False
                break
            elif i == d-1:
                flag3 = True
                break
            elif s3[i] == ".":
                block = 0
            elif s3[i] == "#":
                block += 1

if flag1 or flag3:
    print("Yes")
else:
    print("No")
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value

## BFS

#入力受け取り
N, Q = mi()
x = li2(N-1)

cnt = [0]*N
for i in range(Q):
    p0, p1 = mi()
    cnt[p0] += p1

#隣接リスト作成
adj = [[] for i in range(N)]
for i in range(N-1):
    #x[i][0] -= 1
    #x[i][1] -= 1
    adj[x[i][0]].append(x[i][1])
    adj[x[i][1]].append(x[i][0])

global ans
ans = [0]*(N+1)

def dfs(fr, nx):
    ans[nx] += ans[fr] + cnt[nx]
    for v in adj[nx]:
        if v != fr:
            dfs(nx, v)

dfs(1, 1)

for i in range(1, N+1):
    print(ans[i], '', end='')

### FIXED CODE ###

import sys
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]
import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value
'''
from collections import deque
N, Q = mi()
D = li2(N-1)
px = li2(Q)
que = deque()

adj = [[] for i in range(N+1)]

for i in range(N-1):
    adj[D[i][0]].append(D[i][1])

ans = [0]*(N+1)
for j in range(Q):
    ind, a = px[j][0], px[j][1]
    que.append(ind)
    while(que!=deque()):
        v = que.popleft()
        ans[v] += a
        for e in adj[v]:
            que.append(e)


for i in range(1, N+1):
    print(ans[i], ' ', end='')
'''

from collections import deque
sys.setrecursionlimit(10**9)

#入力受け取り
N, Q = mi()
x = li2(N-1)
#p = li2(Q)

cnt = [0]*N
for i in range(Q):
    p0, p1 = mi()
    cnt[p0-1] += p1

#隣接リスト作成
adj = [[] for i in range(N)]
for i in range(N-1):
    x[i][0] -= 1
    x[i][1] -= 1
    adj[x[i][0]].append(x[i][1])
    adj[x[i][1]].append(x[i][0])

que = deque()
ans = [0]*N

#for a in range(N):
que.append((0, 0))
num = 0
while que!=deque():
    v = que.popleft()
    ans[v[1]] = ans[v[0]] + cnt[v[1]]
    for next in adj[v[1]]:
        if next != v[0]:
            que.append((v[1], next))

for k in ans:
    print(k, '', end='')
#n>=25なら鳩ノ巣で0
#2人以上居るdは一意
#あとはしらみつぶし

n = int(input())
if n>=25:
    print(0)
    exit()

d = list(map(int, input().split( )))
if 0 in d:##
    print(0)
    exit()
d.append(0)
dic = {}

for di in d:
    if di in dic:
        dic[di] += 1
    else:
        dic[di]= 1
solo = []
times = []
for di in dic:
    if dic[di]==1:#di=0はここに入る
        solo.append(di)
    elif dic[di]==2:
        times.append(di)
        times.append(24-di)
    else:
        print(0)
        exit()
        
ans = 0
m = len(solo)
bit = 1<<m

for i in range(bit):
    times2 = []
    for t in times:
        times2.append(t)
    for j in range(m):
        if i>>j&1:
            times2.append(solo[j])
        elif solo[j]:
            times2.append(24-solo[j])
    times2.sort()
    dif = 24
    if not len(time2):###
        print(0)
        exit()
    #print(times2)

    for k in range(len(times2)-1):
        dif = min(dif,times2[k+1]-times2[k])
    ans = max(ans,dif)
print(ans)
 

### FIXED CODE ###

#n>=25なら鳩ノ巣で0
#2人以上居るdは一意
#あとはしらみつぶし

n = int(input())
if n>=25:
    print(0)
    exit()

d = list(map(int, input().split( )))
if 0 in d:##
    print(0)
    exit()
d.append(0)
dic = {}

for di in d:
    if di in dic:
        dic[di] += 1
    else:
        dic[di]= 1
solo = []
times = []
for di in dic:
    if dic[di]==1:#di=0はここに入る
        solo.append(di)
    elif dic[di]==2:
        times.append(di)
        if di!=12:
            times.append(24-di)
        else:
            print(0)
            exit()
    else:
        print(0)
        exit()
        
ans = 0
m = len(solo)
bit = 1<<m

for i in range(bit):
    times2 = []
    for t in times:
        times2.append(t)
    for j in range(m):
        if i>>j&1:
            times2.append(solo[j])
        else:####???
            times2.append(24-solo[j])
    times2.sort()
    dif = 24
    if len(times2)==1:###
        print(0)
        exit()
    #print(times2)

    for k in range(len(times2)-1):
        dif = min(dif,times2[k+1]-times2[k])
    dif = min(dif,times2[0] + 24 - times2[-1])
    ans = max(ans,dif)
print(ans)
N = int(input())
A = map(int, input().split())

sub = [0 for i in range(N)]

for a in A:
    sub[a - 1] += 1

for s in sub:
    print(s)
j

### FIXED CODE ###

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

sub = [0 for i in range(N)]

for a in A:
    sub[a - 1] += 1

for s in sub:
    print(s)
h,n=map(int,input().split())
ab=[list(map(int,input().split())) for _ in range(n)]

max_a=max(a for a,_ in ab)
dp = [0] * (h+max_a)

for i in range(0,h+max_a):
    if i==0:
        d[i]=0
    else:
        dp[i]=min(dp[i-a]+b for a,b in ab)
print(min(dp[h:]))


### FIXED CODE ###

h, n = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(n)]

max_a = max(a for a, _ in ab)
dp = [0] * (h+max_a)

for i in range(0, h+max_a):
    if i <= 0:
        dp[i] = 0
    else:
        dp[i] = min(dp[i-a] + b for a,b in ab) 

print(min(dp[h:]))