Harryxun/stf_run huggingface dataset:
N,M = map(int,input().split())
A = list(map(int,input().split()))
A.sort()
A.reverse()
match = [2,5,5,4,5,6,3,7,6]
dp = [0]*(N+1)
for i in range(N+1):
  kouho = 0
  for j in range(M):
    if i-match[A[j]-1] >= 0:
      if kouho < dp[i-match[A[j]-1]]+1:
        kouho = dp[i-match[A[j]-1]]+1
  dp[i] = kouho
ans = ''
while N > 0:
  for i in range(M):
    if dp[N-match[A[i]-1]] == dp[N]-1:
      if dp[N]-1 != 0:
        ans += str(A[i])
        N -= match[A[i]-1]
        break
      else:
        for k in range(M):
          if match[A[k]-1] == N:
            ans += str(A[k])
            N = 0
            break
print(ans)

### FIXED CODE ###

n,m = map(int,input().split())
A = list(map(int,input().split()))
L = [2,5,5,4,5,6,3,7,6]
dp = [-float('inf')]*(n+1)
dp[0] = 0
for i in range(1,n+1):
    for j in range(m):
        if i-L[A[j]-1] < 0:
            None
        else:
            dp[i] = max(dp[i-L[A[j]-1]]+1, dp[i])
A.sort()
A.reverse()
cur = n
ans = ''
while cur != 0:
    for i in range(m):
        temp = A[i]
        if cur-L[temp-1] >= 0:
            if dp[cur-L[temp-1]] == dp[cur]-1:
                ans = ans+str(temp)
                cur -= L[temp-1]
                break
print(ans)
c = map(int,input().split())
if c[0] < c[2] and c[2] < c[1]:
  print('Yes')
  exit()
if c[0] > c[2] and c[2] > c[1]:
  print('Yes')
  exit()
print('No')

### FIXED CODE ###

#a.py
A,B,C = map(int,input().split())
if A < C and C < B:
  print('Yes')
  exit()
if B < C and C < A:
  print('Yes')
  exit()
print('No')
import math
n=int(input())
li = list(map(int,input().split()))
a=li[0]
for i in range(n):
    a=math.gcd(li[i],a)
print(a)


### FIXED CODE ###

def gcd(a, b):
	while b:
		a, b = b, a % b
	return a
n=int(input())
li = list(map(int,input().split()))
a=li[0]
for i in range(n):
    a=gcd(li[i],a)
print(a)
print("YES" if input() == reversed(input()) else "No)

### FIXED CODE ###

print("YES" if input() == "".join(list(reversed(input()))) else "NO")
s = input()
t = set(s)
if len(t) == 2 and s.count(t[0]) == 2:
  print("Yes")
else:
  print("No")

### FIXED CODE ###

s = input()
t = set(s)
if len(t) == 2 and s.count(list(t)[0]) == 2:
  print("Yes")
else:
  print("No")
x = input()
if x >= 30:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

x = int(input())
if x >= 30:
    print("Yes")
else:
    print("No")
N = int(input())
l = len(N)
for i in range(l):
  if N[i] ==7:
    print("Yes")
    exit()
print("No")    

### FIXED CODE ###

N = input()
l = len(N)
for i in range(l):
  if N[i] =="7":
    print("Yes")
    exit()
print("No")
def solve():
    from sys import stdin
    f_i = stdin
    
    N = int(f_i.readline())
    
    points = []
    for i in range(N):
        x, y = map(int, f_i.readline().split())
        points.append(x + y * 1j)
    
    radiuses = []
    from itertools import combinations
    err = 10 ** -7
    for p1, p2 in combinations(points, 2):
        c = (p1 + p2) / 2
        r = abs(p1 - c)
        for p in points:
            d = abs(p - c)
            if d - r > err:
                break
        else:
            radiuses.append(r)
    
    print(min(radiuses))

solve()

### FIXED CODE ###

def solve():
    from sys import stdin
    f_i = stdin
    
    N = int(f_i.readline())
    
    points = []
    for i in range(N):
        x, y = map(int, f_i.readline().split())
        points.append(x + y * 1j)
    
    from itertools import combinations
    radiuses = []
    
    for p1, p2 in combinations(points, 2):
        c = (p1 + p2) / 2
        r = abs(p1 - c)
        for p in points:
            if abs(p - c) > r:
                break
        else:
            radiuses.append(r)
    
    if radiuses:
        return min(radiuses)
    
    def circumcircle(a, b, c):
        n = (a - b) * abs(c) ** 2 + (b - c) * abs(a) ** 2 + (c - a) * abs(b) ** 2
        d = (a - b) * c.conjugate() + (b - c) * a.conjugate() + (c - a) * b.conjugate()
        return n / d # center of circumcircle
    
    err = 10 ** -7
    for p1, p2, p3 in combinations(points, 3):
        z1 = p3 - p1
        z2 = p2 - p1
        if z1.real * z2.imag == z1.imag * z2.real:
            continue
        
        c = circumcircle(p1, p2, p3)
        r = abs(p1 - c)
        for p in points:
            #if abs(p - c) > r:
            if abs(p - c) - r > err:
                break
        else:
            radiuses.append(r)
    
    return min(radiuses)

print(solve())
N, A, B = map(int, input().split())

que = []

for i in range(N//(A+B)+1):
    for j in range(A):
        que.append('b')
    for j in range(B):
        que.append('r')

count = 0
for i in range(N):
    if que[i] == 'b':
        count += 1

print(count)

### FIXED CODE ###

S = input()

if S[0] == S[1] and S[0] == S[2]:
    print('No')
else:
    print('Yes')
N = int(intpu())
ans = 1
while True:
  ans *= 2
  if N < ans:
    ans //= 2
    break
    
print(ans)

### FIXED CODE ###

N = int(input())
ans = 1
while True:
  ans *= 2
  if N < ans:
    ans //= 2
    break
    
print(ans)
A, B = map(int,input().split())
mod = 10**9+7
def factorical(n):
  ret = 1
  for i in range(1,n+1):
    ret *= i
    ret %= 
  return ret%mod

a = factorical(A)
b = factorical(B)
if(abs(A-B) >= 2):
  print(0)
elif(A == B):
  print(a*b*2%mod)
else:
  print(a*b%mod)

### FIXED CODE ###

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

def factorical(n):
  ret = 1
  for i in range(1,n+1):
    ret *= i
    ret %= 10**9+7
  return ret

diff = abs(N - M)
max_ = int(1e9+7)

if(diff >= 2):
  print(0)
elif(diff == 1):
  n = N % max_
  m = M % max_
  print((factorical(n)*factorical(m)) % max_)
else:
  n = N % max_
  m = M % max_
  print((2*factorical(n)*factorical(m)) % max_)
import sys

readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines


def main():
    N = int(readline())
    S = list(map(lambda x: x.decode("UTF-8"), readlines()))
    S = list(map(lambda x: x.rstrip('\n'), S))
    march = list("MARCH")

    cnt = [0] * 5
    for i in range(N):
        for j in range(5):
            if S[i][0] == march[j]:
                cnt[j] += 1

    ans = 0
    for i in range(N-2):
        for j in range(i+1, N-1):
            for k in range(j+1, N):
                ans += cnt[i] * cnt[j] * cnt[k]

    print(ans)


main()


### FIXED CODE ###

def main():
    N = int(input())

    cnt = [0]*5
    for i in range(N):
        S = input()
        if S[0] == 'M':
            cnt[0] += 1
        if S[0] == 'A':
            cnt[1] += 1
        if S[0] == 'R':
            cnt[2] += 1
        if S[0] == 'C':
            cnt[3] += 1
        if S[0] == 'H':
            cnt[4] += 1

    ans = 0
    for i in range(3):
        for j in range(i+1, 4):
            for k in range(j+1, 5):
                ans += cnt[i] * cnt[j] * cnt[k]

    print(ans)


main()
[n,t]=list(map(int,input().split()))
alist=list(map(int,input().split()))

"""
alist.reverse()
n=n-1
dp=[[0 for j in range(n)]for k in range(n)]
for i in range(n-1):
	dp[i][i+1]=alist[i+1]-alist[i]
	
for i in reversed(range(0,n-1)):
	for j in range(n-1-i):
		dp[i][i+2+j]=dp[i][i+1]+dp[i+1][i+2+j]

maximum=max(dp[0])
for i in range(1,n):
	if maximum<max(dp[i]):
		maximum=max(dp[i])
kosu=0
for i in range(0,n):
	kosu=kosu+dp[i].count(maximum)
print(kosu)
"""

salist=[]
for i in range(n-1):
	saisho=min(alist[0:i])
	salist.append(alist[i+1]-saisho)
saidai=max(salist)
kaisu=salist.count(saidai)
print(kaisu)

### FIXED CODE ###

[n,t]=list(map(int,input().split()))
alist=list(map(int,input().split()))
salist=[alist[1]-alist[0]]
saisho=min(alist[0],alist[1])
for i in range(1,n-1):
	saisho=min(saisho,alist[i])
	salist.append(alist[i+1]-saisho)
saidai=max(salist)
kaisu=salist.count(saidai)
print(kaisu)
import sys
s=input()
if len(s)==26:
    if s=="zyxwvutsrqponmlkjihgfedcba":
        print(-1)
        sys.exit()
    for i in range(25):
        if ord(s[i])+1==ord(s[i+1]):
            continue
        else:
            s=s[:i]
            break
    se=set(s)
    p=sorted(list(set(s)))
    moji=[]
    alphabet=[chr(i) for i in range(97, 97+26)]
    for i in range(26):
        if alphabet[25-i] not in se:
            
            moji.append(alphabet[25-i])
    print(s+moji[len(moji)-2])
else:
    se=set(s)
    p=sorted(list(set(s)))
    alphabet=[chr(i) for i in range(97, 97+26)]
    for i in range(26):
        if alphabet[25-i] not in se:
            moji=alphabet[25-i]
    print(s+moji)

### FIXED CODE ###

import sys
from collections import Counter
s=input()
count=Counter(s)
alphabets=[chr(ord("a")+i) for i in range(26)]
if s=="zyxwvutsrqponmlkjihgfedcba":
    print(-1)
    sys.exit()

if len(count) <26:
    for i in range(26):
        if alphabets[i] not in count:
            print(s+alphabets[i])
            sys.exit()

for i in range(25):
    if ord(s[25-i])<ord(s[24-i]):
        continue
    else:
        memo=s[24-i]
        break
lst=sorted(list("qwertyuiopasdfghjklzxcvbnm"))
for j in range(24-i):
    lst.remove(s[j])
moji=lst[lst.index(memo)+1]
print(s[:24-i]+moji)
n=input()
kagami=[]
for i in range(n):
    d=input()
    if d not in kagami:
        kagami.append(d)
print(len(kagami))


### FIXED CODE ###

n=int(input())
kagami=[]
for i in range(n):
    d=input()
    if d not in kagami:
        kagami.append(d)
print(len(kagami))
import math
while Ture:
	n = int(raw_input())
	if n==0:
		break
	sum = 0
	for i in xrange(n):
		s = map(int,raw_input())
		sum += s
	ave = sum/n
	sum = 0
	for i in xnrange(n):
		sum += pow(s[i] - ave,2.0)
	print math.sqrt(sum/n)
	

### FIXED CODE ###

import math
while True:
	n = int(raw_input())
	if n==0:
		break
	s = map(int,raw_input().split())
	ave = sum = 0.0
	for i in xrange(n):
		ave += s[i]
	ave /= n
	for i in xrange(n):
		sum += math.pow(s[i] - ave, 2.0)
	print math.sqrt(sum/n)
import math

N = int(input())
tmp = []
for i in range(1, int(math.sqrt(N))):
    v = N % i
    if v == 0:
        mult = N / i
        tmp.append(int(i + mult - 2))
print(min(tmp))

### FIXED CODE ###

N = int(input())
max = int(N**0.5)
a = max-1
for i in range(max,0,-1):
    v = N % i
    if v == 0:
        mult = N / i
        a = mult + i
        break
print(int(a-2))
# D - Disjoint Set of Common Divisors
A, B = map(int, input().split())

from fractions import gcd

# n以下の素数列挙 O(n log(n))
def primes(n):
    ass = []
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    for i in range(len(is_prime)):
        if is_prime[i]:
            ass.append(i)
    return ass

ans = 0
for pr in primes(gcd(A, B)):
    if A%pr == 0 and B%pr == 0:
        ans += 1

print(ans+1)
# 1は素数に含まれないが今回の問題の回答に含まれるので+1

### FIXED CODE ###

# D - Disjoint Set of Common Divisors
A, B = map(int, input().split())

from fractions import gcd

# nの素数判定
def is_prime(n):
    if n == 1:
        return False
    for i in range(2,int(n**0.5)+1):
        if n % i == 0:
            return False
    return True

# nの約数列挙
def divisor(n):
    ass = []
    for i in range(1,int(n**0.5)+1):
        if n%i == 0:
            ass.append(i)
            ass.append(n//i)
    return ass #sortされていない

ans = 0
gcd1 = gcd(A, B)
for i in divisor(gcd1):
    if is_prime(i):
        ans += 1

print(ans+1)
import math
from math import atan, cos, tan

a, b, x = map(int, input().split()  ) #split()で分解したものを別々の変数に入れる

result =0

if x>=a**2 * b/2:
    result = math.degrees(math.pi /2 - atan(a/ (2*(b - x/a**2))))
else:
    result = math.degrees(math.pi /2 - atan(2*x/(a*b)/b))

print(result)

### FIXED CODE ###

import math
from math import atan, cos, tan

a, b, x = map(int, input().split()  ) #split()で分解したものを別々の変数に入れる

result =0

if x>=a**2 * b/2:
    result = math.degrees(atan((2*(b - x/a**2)/a)))
else:
    result = math.degrees(atan(a*b**2/2/x))

print(result)
import sys
input = sys.stdin.readline

if __name__ == '__main__':
  n=int(input())
  #A=list(map(int,input().strip("\n").split()))
  A=input().strip("\n")
  q=int(input())
  Ans=[]
  for i in range(q):
    #b,c=map(int,input().strip("\n").split())
    b,c=input().strip("\n").split()
    A=A.replace(b,c)
    Ans.append(eval(A.replace(" ","+")))
  for ans in Ans:
    print(ans)


### FIXED CODE ###

import sys
input = sys.stdin.readline

if __name__ == '__main__':
  n=int(input())
  A_str=input().strip("\n")
  A=A_str.split()
  q=int(input())

  C={}
  for a in A:
    if a in C:
      C[a]+=1
    else:
      C[a]=1
  
  def rep(b,c):
    if c in C:
      C[c]+=C[b]
    else:
      C[c]=C[b] 
    C[b]=0
    #print(b,c,C)

  Ans=[]
  ans=''
  b,c=input().strip("\n").split()
  #tmp=eval(A_str.replace(b,c).replace(" ","+"))
  tmp=0
  hoge=map(int,A)
  for a in hoge:
    if str(a)==b:
      tmp+=int(c)
    else:
      tmp+=a
  #ans+=str(tmp)
  #ans+="\n"
  Ans.append(tmp)
  if b in C:
    rep(b,c)
  for i in range(1,q-1):
    b,c=input().strip("\n").split()
    if b in C:
      tmp+=(int(c)-int(b))*C[b]
      rep(b,c)
    #ans+=str(tmp)+"\n"
    Ans.append(tmp)
  b,c=input().strip("\n").split()
  if b in C:
    tmp+=(int(c)-int(b))*C[b]
  #ans+=str(tmp)
  Ans.append(tmp)
  #print(ans)
  for ans in Ans:
    print(ans)
T = input()
T = list(T)
N = len(T)
  if T[i] =='?'
    del T[i]   
    T.insert(i,'D')
print("".join(T))

### FIXED CODE ###

S = input()
s=[]
for i in S:
    s.append(i)
t = []
for i in range(len(s)):
  if s[i] == '?':
    t.append('D')
  else:
    t.append(s[i])
Strt = "".join(t)
print(Strt)
print("TFhoruere"[len(set(map(int, open(0).read().split())))-4::2])

### FIXED CODE ###

print("TFhoruere"[len(set(open(0).read().split()))-4::2])
n=int(input())
ans=0
for i in range(1,n-1):
  p=max(l[i-1],l[i+1])
  q=min(l[i-1],l[i+1])
  if q<=l[i]<=p:ans+=1
print(ans)

### FIXED CODE ###

n=int(input())
ans=0
l=list(map(int,input().split()))
for i in range(1,n-1):
  p=max(l[i-1],l[i+1])
  q=min(l[i-1],l[i+1])
  if q<=l[i]<=p:ans+=1
print(ans)
import math
n = int(input())
a = list(map(int,input().split()))
mx = max(a)
b=[0] * mx
ans = 0
for i in range(n):
    b[a[i]-1] += 1

for i in range(mx):
    if(b[i] == 0 or b[i] == 1):
        ans += 0
    else:
        ans = ans + math.factorial(b[i])/2 / math.factorial(b[i]-2)
ans1 = 0


for i in range(n):
    ans1 = ans -(math.factorial(b[a[i]-1])/2 / math.factorial(b[a[i]-1]-2))
    if(b[a[i]-1]-1 < 2):
        print(int(ans1))
    else:
        ans1 = ans1 + (math.factorial(b[a[i]-1]-1)/2 / math.factorial(b[a[i]-1]-3))
        print(int(ans1))

### FIXED CODE ###

import math
n = int(input())
a = list(map(int,input().split()))
mx = max(a)
b=[0] * 2000000
ans = 0
for i in range(len(a)):
    b[a[i]-1] += 1

for i in range(mx):
    if(b[i] == 0 or b[i] == 1):
        ans += 0
    else:
        ans = ans + int(b[i] * (b[i]-1)/2)
ans1 = 0


for i in range(len(a)):
    ans1 = ans
    if(b[a[i]-1] >2):
        ans1 = ans1 -int((b[a[i]-1]*(b[a[i]-1]-1))/2) + int(((b[a[i]-1]-1) * (b[a[i]-1]-2))/2)
        print(int(ans1))
    elif(b[a[i]-1] == 2):
        print(int(ans1-1))
    elif(b[a[i]-1] < 2):
        print(int(ans1))
#coding:utf-8

import sys

N = int(input())
S = input()

T = len(S)

for t in reversed(range(T+1)):
    i = 0
    while 0 < len(S[i:i+t-1]) and len(S[i:i+t-1]) <= len(S[i+t-1:]):
        if S[i:i+t-1] in S[i+t-1:]:
            print(len(S[i:i+t-1]))
            sys.exit()
        i += 1
print('0')


### FIXED CODE ###

#coding:utf-8

S = input()

if S == 'Sunny':
    print('Cloudy')
elif S == 'Cloudy':
    print('Rainy')
else:
    print('Sunny')
n = int(input())
a = [int(i) for i in input().split()]
q = int(input())
num = [0] * 100010
b = [0] * q
c = [0] * q
for i in range(q):
    b[i], c[i] = map(int, input().split())

for i in a:
    num[i] += 1

s = sum(a)

for i in range(q):
    s += (c[i]　-　b[i])　*　num[b[i]]
    num[c[i]] += num[b[i]]
    num[b[i]] = 0
    print(s)

### FIXED CODE ###

n = int(input())
a = [int(i) for i in input().split()]
q = int(input())
num = [0] * 100010
b = [0] * q
c = [0] * q
for i in range(q):
    b[i], c[i] = map(int, input().split())

for i in a:
    num[i] += 1

s = sum(a)

for i in range(q):
  s+=(c[i]-b[i])*num[b[i]]
  num[c[i]] += num[b[i]]
  num[b[i]] = 0
  print(s)
n,q=map(int,input().split())
child=[[] for _ in range(n)]
point=[0 for _ in range(n)]
for i in range(n-1):
    a,b=map(int,input().split())
    child[a-1].append(b-1)

for i in range(q):
    p,x=map(int,input().split())
    point[p-1]+=x

ans=[0 for _ in range(n)]
def dfs(vertex,pt):
    pt_v=pt+point[vertex]
    ans[vertex]=pt_v
    child_v=child[vertex]
    for i in range(len(child_v)):
        dfs(child_v[i],pt_v)


dfs(0,0)

for i in range(n):
    print(ans[i],end=" ")


### FIXED CODE ###

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

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

link=[[] for _ in range(n)]
for _ in range(n-1):
    a,b=map(int,input().split())
    link[a-1].append(b-1)
    link[b-1].append(a-1)

v_counter=[0 for _ in range(n)]
for _ in range(q):
    p,x=map(int,input().split())
    v_counter[p-1]+=x

point=[0 for _ in range(n)]
que=deque()
que.append(0)
used=set()
used.add(0)
point[0] += v_counter[0]

while(len(que)>0):
    ind=que.popleft()
    relate=link[ind]
    for i in relate:
        if(i in used):
            continue
        else:
            point[i] += point[ind] + v_counter[i]
            que.append(i)
            used.add(i)

print(*point)
I0 = lambda :map(int,input().split())
I1 = lambda :int(input())
I2 = lambda :list(map(int,input().split()))
#####################################################
A,B = I0()
print(max([A*B,A-B,A+b]))


### FIXED CODE ###

I0 = lambda :map(int,input().split())
I1 = lambda :int(input())
I2 = lambda :list(map(int,input().split()))
#####################################################
A,B = I0()
print(max([A*B,A-B,A+B]))
n = int(input())  # nは入力回数
num_list = list(map(int, input().split()))
count = 0

if n//2 == 0:
  for i in range(n//2):
    if (num_list[2*i]%2) == 1:
      count += 1
else:
  for i in range((n//2) + 1):
    if (num_list[2*i]%2) == 1:
      count += 1
      
print(count)

### FIXED CODE ###

n = int(input())  # nは入力回数
num_list = list(map(int, input().split()))
count = 0

if n%2 == 0:
  for i in range(n//2):
    if (num_list[2*i]%2) == 1:
      count += 1
else:
  for i in range((n//2) + 1):
    if (num_list[2*i]%2) == 1:
      count += 1
      
print(count)
x, k, d = map(int ,input().split())
ans_min = x

def dfs(i, ans):
  global ans_min
  if abs(ans_min) > abs(ans) and ans >= 1:
    ans_min = ans
  if i == k:
    return abs(ans_min)
  dfs(i + 1, ans + d)
  dfs(i + 1, ans - d)

dfs(0, x)
print(ans_min)

### FIXED CODE ###

x, k, d = map(int, input().split())

x = abs(x)
straight = min(k, x//d)
k -= straight
x -= straight*d

if k%2 == 0:
  print(x)
else:
  print(d-x)
s = list(input())
al = list("abcdefghijklmnopqrstuvwxyz")
if s[0] == "A" and s[-1] in al and s[1] in al:
    del s[0]
    del s[0]
    del s[-1]
    f = 0
    for i in s:
        if i == "C":
            if f == 1:
                print("WA")
                break
            else:
                f = 1
                continue
        else:
            if i in al:
                continue
            else:
                print("WA")
                break
    else:
        if f = 1:
            print("AC")
        else:
            print("WA")
else:
    print("WA")

### FIXED CODE ###

s = list(input())
al = list("abcdefghijklmnopqrstuvwxyz")
if s[0] == "A" and s[-1] in al and s[1] in al:
    del s[0]
    del s[0]
    del s[-1]
    f = 0
    for i in s:
        if i == "C":
            if f == 1:
                print("WA")
                break
            else:
                f = 1
                continue
        else:
            if i in al:
                continue
            else:
                print("WA")
                break
    else:
        if f == 1:
            print("AC")
        else:
            print("WA")
else:
    print("WA")
L, R = [[], []]
N, M = map(int, input().split())
for i in range(M):
  l, r = map(int, input().split())
  L.append(l)
  R.append(r)

minR = min(R)
maxL = max(L)
if minR <= maxL:
  count = 0
else:
  count = minR - maxL + 1
      
print('%d' % count)

### FIXED CODE ###

A, B = map(int, input().split())
if A>=13:
  cost = B
elif A>=6 and A<=12:
  cost = B/2
else:
  cost = 0
print('%d' % cost)
from math import ceil
sys.setrecursionlimit(10**6)
def main():
    INF = 10**9
    h,n = map(int,input().split())
    spell = []
    for _ in range(n):
        spell.append(tuple(map(int,input().split())))

    dp = [[INF]*(h+1) for _ in range(n+1)]

    for i,item in enumerate(spell):
        a,b = item
        for j in range(h):
            if j-a<0:
                dp[i+1][j+1] = min(dp[i][j+1],b*ceil((j+1)/a))
            else:
                dp[i+1][j+1] = min(dp[i][j+1],dp[i+1][j+1-a]+b)
        
    print(dp[n][h])
main()

### FIXED CODE ###

def ceil(x,p):
    if x%p==0:
        return x//p
    else:
        return x//p+1

def main():
    INF = 10**9
    h,n = map(int,input().split())
    spell = []
    for _ in range(n):
        spell.append(tuple(map(int,input().split())))

    dp = [[INF]*(h+1) for _ in range(n+1)]

    for i,item in enumerate(spell):
        a,b = item
        for j in range(h):
            if j-a<0:
                dp[i+1][j+1] = min(dp[i][j+1],b*ceil(j+1,a))
            else:
                dp[i+1][j+1] = min(dp[i][j+1],dp[i+1][j+1-a]+b)
        
    print(dp[n][h])
main()
from operator import itemgetter
import numpy

N, M = map(int,input().split())
a = []

D = 0
X = 0
for i in range(N):
    a.append(list(map(int,input().split())))
a.sort(key = itemgetter(0))

for i in range(N):
    D += a[i][1]
    if D>M:
        for k in range(i+1):
            X += a[k][0]*a[k][1]
            Y = X-(D-M)*a[i][0]
        break
print(Y)


### FIXED CODE ###

from operator import itemgetter

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


a = [list(map(int,input().split())) for i in range(N)]

if N ==1:
    Z = M*a[0][0]
    print(Z)
else:
    a.sort(key = itemgetter(0))
    X = 0 
    D = 0
    var=0
    while M>D:
        D+=a[var][1]
        X+=a[var][0]*a[var][1]
        var+=1
        
    X += a[var-1][0]*(M-D)
    print(X)
S,T=list(input())
s,t=list(map(int, input().split()))
U=input()
if U==S:
  print(s-1,t)
else:
  print(s,t-1

### FIXED CODE ###

S,T=input().split()
s,t=list(map(int, input().split()))
U=input()
if U==S:
  print(s-1,t)
else:
  print(s,t-1)
X=input()
if X<30:
    print("NO\n")
else:
    print("YES\n")


### FIXED CODE ###

X=int(input())
if X<30:
    print("No")
else:
    print("Yes")
import sys
N, X = map(int, input().split())
L = list(map(int, input().split()))
cnt = 0
total = 0
for i in range(N+1):
  if total <= X:
    cnt += 1
    total += L[i]
  else:
    print(cnt)
    sys.exit()
print(N+1)


### FIXED CODE ###


N, X = map(int, input().split())
L = list(map(int, input().split()))
cnt = 1
total = 0
for i in range(N):
  total += L[i]
  if total <= X:
    cnt += 1
  else:
    break
print(cnt)
import sympy

N = int(input())

ans = 0
for x in range(1, N+1):
    ans += x * sympy.divisor_count(x)
print(ans)

### FIXED CODE ###

N = int(input())

ans = 0
for i in range(1,N+1):
    k = N // i
    ans += (i + i*k) * k // 2
print(ans)
S=input()
flag = False
if S=="zyxwvutsrqponmlkjihgfedcba":
    T="-1"
elif len(S)<=25:
    for i in range(97,123):
        if chr(i) not in S:
            T=S+chr(i)
            break
else:
    for i in range(2,26):
        for j in range(ord(S[-i])+1,123):
            if chr(j) not in S[:-i]:
                T=S[:-i]+chr(j)
                flag=True
                break
        if flag:
            break
print(T)

### FIXED CODE ###

S=input()
flag = False
if S=="zyxwvutsrqponmlkjihgfedcba":
    T="-1"
elif len(S)<=25:
    for i in range(97,123):
        if chr(i) not in S:
            T=S+chr(i)
            break
else:
    for i in range(2,27):
        for j in range(ord(S[-i])+1,123):
            if chr(j) not in S[:-i]:
                T=S[:-i]+chr(j)
                flag=True
                break
        if flag:
            break
print(T)
n = input()
s = set()
for c in n:
  s.add(c)
if s.len() == 4:
  print("Good")
else:
  print("Bad")

### FIXED CODE ###

n = input()
for i in range(0, 3):
  if n[i] == n[i+1]:
    print("Bad")
    exit(0)
print("Good")