Problem:
 Score : 500 points    Problem Statement Ibis is fighting with a monster.  The health of the monster is H .  Ibis can cast N kinds of spells. Casting the i -th spell decreases the monster's health by A_i , at the cost of B_i Magic Points.  The same spell can be cast multiple times. There is no way other than spells to decrease the monster's health.  Ibis wins when the health of the monster becomes 0 or below.  Find the minimum total Magic Points that have to be consumed before winning.      Constraints  1 \leq H \leq 10^4  1 \leq N \leq 10^3  1 \leq A_i \leq 10^4  1 \leq B_i \leq 10^4  All values in input are integers.         Input Input is given from Standard Input in the following format:  H  N  A_1  B_1  :  A_N  B_N       Output Print the minimum total Magic Points that have to be consumed before winning.        Sample Input 1 9 3
8 3
4 2
2 1      Sample Output 1 4  First, let us cast the first spell to decrease the monster's health by 8 , at the cost of 3 Magic Points. The monster's health is now 1 .  Then, cast the third spell to decrease the monster's health by 2 , at the cost of 1 Magic Point. The monster's health is now -1 .  In this way, we can win at the total cost of 4 Magic Points.       Sample Input 2 100 6
1 1
2 3
3 9
4 27
5 81
6 243      Sample Output 2 100  It is optimal to cast the first spell 100 times.       Sample Input 3 9999 10
540 7550
691 9680
700 9790
510 7150
415 5818
551 7712
587 8227
619 8671
588 8228
176 2461      Sample Output 3 139815

Solution (Python):

def main():
    H, N = map(int, input().split())
    AB = [tuple(map(int, input().split())) for i in range(N)]

    dp = [-1]*(H+1)
    dp[H] = 0

    for i in range(H, 0, -1):
        for a, b in AB:

            if dp[i] >= 0:
                next = max(i-a, 0)
                if dp[next] < 0:
                    dp[next] = dp[i] + b
                else:
                    if dp[next] > dp[i] + b:
                        dp[next] = dp[i] + b

    print(dp[0])
main()

Solution (Python):
H, N = map(int, input().split())
magics = [tuple(map(int, input().split())) for _ in range(N)]
maxA = max([x for x, y in magics])

dp = [10**18]*(H+maxA+1)
dp[0] = 0

for i in range(1, H+maxA+1):
    for j in range(N):
        a, b = magics[j]
        if a<=i:
            dp[i] = min(dp[i-a]+b, dp[i])

print(min(dp[H:]))

Solution (Python):
def main():
    import sys
    input = sys.stdin.buffer.readline
    H, N = (int(i) for i in input().split())
    AB = [[int(i) for i in input().split()] for j in range(N)]
    dp = [[10**9]*(H+1) for _ in range(N+1)]
    dp[0][0] = 0
    for i in range(N):
        for j in range(H+1):
            nH = max(0, j-AB[i][0])
            dp[i+1][j] = min(dp[i][j], dp[i+1][j],
                             dp[i+1][nH] + AB[i][1])
    ans = 10**9
    for i in range(N+1):
        ans = min(ans, dp[i][H])
    print(ans)
    


if __name__ == '__main__':
    main()

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

h, n = map(int, readline().split())
ab = [list(map(int, readline().split())) for _ in range(n)]
inf = float('inf')
dp = [inf] * (h + 1)
dp[0] = 0
for a, b in ab:
    for j in range(h):
        if dp[j] != inf:
            if a + j > h:
                dp[-1] = min(dp[-1], dp[j] + b)
            else:
                dp[a + j] = min(dp[a + j], dp[j] + b)
print(dp[-1])

Solution (Python):
import sys
input = sys.stdin.readline
H, N = map(int, input().split())
dp = [float("inf")] * (H + 1)
dp[H] = 0
for _ in range(N):
  a, b = map(int, input().split())
  for x in range(H, -1, -1):
    dp[max(0, x - a)] = min(dp[max(0, x - a)], dp[x] + b)
print(dp[0])

Solution (Python):
H, N = map(int, input().split())
AB = [tuple(map(int, input().split())) for _ in range(N)]

dp = [10**18] * (H + 1)
dp[0] = 0
for a, b in AB:
    for h in range(H + 1):
        r = min(H, h + a)
        if dp[r] > dp[h] + b:
            dp[r] = dp[h] + b
print(dp[H])

Solution (Python):

h,n = list(map(int,input().split()))
inf = 100000000000000000000
dp = [inf]*(2*100000)
for i in range(-1,-100000,-1):
    dp[i] = 0
ls = [0]*n
for i in range(n):
    ls[i] = list(map(int,input().split()))
dp[0] = 0
for i in range(h):
    for j in range(n):
        dp[i+1] = min(dp[i+1],dp[i+1-ls[j][0]]+ls[j][1])
print(dp[h])

Solution (Python):
h,n=map(int,input().split())
ab=[list(map(int,input().split())) for _ in range(n)]
dp=[float('inf')]*(h+10**4+1)
dp[0]=0
for i in range(h+10**4+1):
  for j in range(n):
    if i-ab[j][0]>=0:
      dp[i]=min(dp[i-ab[j][0]]+ab[j][1],dp[i])
print(min(dp[h:]))

Solution (Python):
def solve():
    H,N = map(int,input().split())
    attack = []
    mp = []
    for i in range(N):
        a,b = map(int,input().split())
        attack.append(a)
        mp.append(b)
    
    max_attack = max(attack)
    dp = [[float('inf')] * (H+max_attack) for _ in range(N+1)]

    for i in range(N+1):
        dp[i][0] = 0
    
    for i in range(N):
        for j in range(H+max_attack):
            if j - attack[i] >= 0:
                dp[i+1][j] = min(dp[i+1][j], dp[i][j-attack[i]]+mp[i], dp[i+1][j-attack[i]]+mp[i])
            dp[i+1][j] = min(dp[i+1][j], dp[i][j])
    
    ans = float('inf')
    for i in range(N+1):
        for j in range(H,H+max_attack):
            ans = min(ans, dp[i][j])
    
    print(ans)

if __name__ == '__main__':
    solve()

Solution (Python):
def solve():
    H,N = map(int,input().split())
    attack = []
    mp = []
    for i in range(N):
        a,b = map(int,input().split())
        attack.append(a)
        mp.append(b)
    
    max_attack = max(attack)
    dp = [[float('inf')] * (H+max_attack) for _ in range(N+1)]

    for i in range(N+1):
        dp[i][0] = 0
    
    for i in range(N):
        for j in range(H+max_attack):
            dp[i+1][j] = min(dp[i+1][j], dp[i][j])
            if j - attack[i] >= 0:
                dp[i+1][j] = min(dp[i+1][j], dp[i][j-attack[i]]+mp[i], dp[i+1][j-attack[i]]+mp[i])
    
    ans = float('inf')
    for i in range(N+1):
        for j in range(H,H+max_attack):
            ans = min(ans, dp[i][j])
    
    print(ans)

if __name__ == '__main__':
    solve()

Solution (Python):
from sys import stdin, setrecursionlimit


def main():
    h, n = map(int, stdin.readline().split())
    ab = []
    max_a = 0
    for _ in range(n):
        a, b = map(int, stdin.readline().split())
        if a > max_a:
            max_a = a
        ab.append([a / b, a, b])

    ab.sort(reverse=True)

    dp = [0] * (h + max_a)

    for i in range(h + max_a):
        dp[i] = (i // ab[0][1] + 1) * ab[0][2]

    for i in range(h):
        for j in range(n):
            dp[i + ab[j][1]] = min(dp[i + ab[j][1]], dp[i] + ab[j][2])

    print(min(dp[h - 1:]))


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()

Solution (Python):
H, n = map(int, input().split())

A = [0] * n
B = [0] * n
for i in range(n):
    A[i], B[i] = map(int, input().split())

dp = [float("inf")] * (H + max(A))
dp[0] = 0
for i in range(H):
    for a, b in zip(A, B):
        if dp[i] + b < dp[i+a]:
            dp[i+a] = dp[i] + b
print(min(dp[H:]))

Solution (Python):
def main():
    import sys
    input=sys.stdin.readline
    h,n=map(int,input().split())
    a=[]
    b=[]
    for i in range(n):
        ai,bi=map(int,input().split())
        a.append(ai)
        b.append(bi)
    inf=max(b)*h
    
    
    dp=[inf]*(h+max(a))
    dp[0]=0
    for i in range(h):
        for j in range(n):
            dp[i+a[j]]=min(dp[i+a[j]],dp[i]+b[j])
    print(min(dp[h:]))
    
if __name__ == '__main__':
    main()

Solution (Python):
import numpy as np
h, n = map(int, input().split())
attack = [0] * n
magic = [0] * n

for i in range(n):
    a, b = map(int, input().split())
    attack[i] = a
    magic[i] = b
attack = np.array(attack)
mgic = np.array(magic)

lim = 0
dp = [lim] * (h + 1)
dp = np.array(dp)
dp[0] = 0






for i in range(1, h + 1):
    temp = dp[np.maximum(i - attack, 0)] + magic
    
    dp[i] = np.min(temp)

print(dp[h])

Solution (Python):
import math
H,N = map(int,input().split())
A=[]
B=[]
for i in range(0,N,1):
    a,b = map(int,input().split())
    A.append(a)
    B.append(b)

dp = [[0 for j in range(0,H+1,1)]for i in range(0,N,1)]

for j in range(0,H+1,1):
    dp[N-1][j]=B[N-1]*math.ceil(j/A[N-1])

for i in range(0,N,1):
    dp[i][0]=0

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

print(dp[0][H])

Solution (Python):
h, n = map(int, input().split())
a = [0]*n
b = [0]*n
for i in range(n):
    a[i], b[i] = map(int, input().split())

dp = [[float("inf")]*(h+1) for i in range(n+1)]
for i in range(n+1):
    dp[i][0] = 0
for i in range(n):
    for j in range(h):
        if j+1-a[i] >= 0:
            dp[i+1][j+1] = min(dp[i][j+1], dp[i][j]+b[i], dp[i+1][j+1-a[i]]+b[i])
        else:
            dp[i+1][j+1] = min(dp[i][j+1], dp[i][j]+b[i], b[i])

print(dp[n][h])

Solution (Python):

import math

h,n=map(int,input().split())
ablist=[]
amax=0
for i in range(n):
    a,b=map(int,input().split())
    ablist.append([a,b])
    amax=max(a,amax)

powlist=[]
for i in range(h+amax):
    powlist.append(math.ceil((i+1)/ablist[0][0])*ablist[0][1])

for i in range(1,n):
    for j in range(h+amax):
        if j+1 <= ablist[i][0]:
            powlist[j]=min(powlist[j],ablist[i][1])
        else:
            powlist[j]=min(powlist[j],powlist[j-ablist[i][0]]+ablist[i][1])
            

print(min(powlist[h-1:]))

Solution (Python):
H, N = map(int, input().split())
Attack = []
Magic = []
for _ in range(N):
    a, b = map(int, input().split())
    Attack.append(a)
    Magic.append(b)

DP = [float('inf')] * (H + 1)
DP[0] = 0
for i in range(H):
    for j in range(N):
        d = min(H, i + Attack[j])
        DP[d] = min(DP[d], DP[i] + Magic[j])

print(DP[H])

Solution (Python):
h,n=(int(i) for i in input().split())
l=[]
for i in range(n):
  a,b=(int(i) for i in input().split())
  l.append([a,b])
pocket=[0]
for i in range(h):
  mini=pocket[max(0,i+1-l[0][0])]+l[0][1]
  for j in range(n-1):
    a=l[j+1][0]
    b=l[j+1][1]
    if pocket[max(0,i+1-a)]+b<mini:
      mini=pocket[max(0,i+1-a)]+b
  pocket.append(mini)
print(pocket[h])

Solution (Python):
from operator import itemgetter

INF = 10 ** 10

H, N = map(int, input().split())
AB = [tuple(map(int, input().split())) for _ in range(N)]

A_max = max(map(itemgetter(0), AB))

dp = [INF] * (H + A_max+1)
dp[0] = 0

for i in range(0, H+A_max+1):
    for A, B in AB:
        if A <= i:
            dp[i] = min(dp[i], dp[i-A] + B)

print(min(dp[H:]))

Solution (Python):
h, n = map(int, input().split())

inf = 10**9
magic = []
c = 0
for i in range(n):
	a, b = map(int, input().split())
	magic.append([a,b])
	c = max(c,a)

dp = [inf] * (h+c)

for i, j in magic:
	dp[i] = min(dp[i],j)

for i in range(len(dp)):
	for j in range(n):
		if i - magic[j][0] <= 0 or dp[i-magic[j][0]] == inf:
			continue
		else:
			dp[i] = min(dp[i],dp[i-magic[j][0]] + magic[j][1])

print (min(dp[h:]))

Solution (Python):
h, n = map(int, input().split())

A = [0] * n
B = [0] * n
for i in range(n):
    A[i], B[i] = map(int, input().split())

dp = [float("inf")] * (h+1)
dp[0] = 0

for i in range(h):
    for j in range(n):
        next_index = min(i + A[j], h)
        dp[next_index] = min(dp[next_index], dp[i] + B[j])

print(dp[-1])

Solution (Python):
H, N = map(int, input().split(' '))
magic = [[0 for _ in range(3)] for j in range(N)]
for i in range(N):
  temp_a, temp_b = map(int, input().split())
  magic[i][0] = temp_a
  magic[i][1] = temp_b

dp = [float('inf')] * (H + 1)
dp[0] = 0

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

print(dp[H])

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

h, n = map(int, readline().split())
ab = [list(map(int, readline().split())) for _ in range(n)]
inf = float('inf')
dp = [inf] * (h + 1)
dp[0] = 0
for i, (a, b) in enumerate(ab):
    for j in range(h):
        if j + a >= h:
            dp[-1] = min(dp[-1], dp[j] + b)
        else:
            dp[j + a] = min(dp[j + a], dp[j] + b)
print(dp[-1])

Solution (Python):
from collections import deque
from heapq import heapify,heappop,heappush,heappushpop
from copy import copy,deepcopy
from itertools import permutations,combinations
from collections import defaultdict,Counter
from bisect import bisect_left,bisect_right


from functools import reduce
from pprint import pprint

def myinput():
    return map(int,input().split())

def mylistinput(n):
    return [ list(myinput()) for _ in range(n) ]

def mycol(data,col):
    return [ row[col] for row in data ]

def mysort(data,col,reverse_flag):
    data.sort(key=lambda x:x[col],reverse=reverse_flag)
    return data

def mymax(data):
    M = -1*float("inf")
    for i in range(len(data)):
        m = max(data[i])
        M = max(M,m)
    return M

def mymin(data):
    m = float("inf")
    for i in range(len(data)):
        M = min(data[i])
        m = min(m,M)
    return m

def myoutput(ls,space=True):
    if space:
        if len(ls)==0:
            print(" ")
        elif type(ls[0])==str:
            print(" ".join(ls))
        elif type(ls[0])==int:
            print(" ".join(map(str,ls)))
        else:
            print("Output Error")
    else:
        if len(ls)==0:
            print("")
        elif type(ls[0])==str:
            print("".join(ls))
        elif type(ls[0])==int:
            print("".join(map(str,ls)))
        else:
            print("Output Error")

H,N = myinput()
AB = mylistinput(N)


dp = [float("inf")]*(H+1)
dp[0] = 0

for i in range(1,H+1):
    for j in range(N):
        a = AB[j][0]
        b = AB[j][1]
        if i<a:
            dp[i] = min( dp[i], dp[0]+b )
        else:
            dp[i] = min( dp[i], dp[i-a]+b )

ans = dp[H]
print(ans)

Solution (Python):
from collections import deque
from heapq import heapify,heappop,heappush,heappushpop
from copy import copy,deepcopy
from itertools import permutations,combinations
from collections import defaultdict,Counter
from bisect import bisect_left,bisect_right


from functools import reduce
from pprint import pprint

def myinput():
    return map(int,input().split())

def mylistinput(n):
    return [ list(myinput()) for _ in range(n) ]

def mycol(data,col):
    return [ row[col] for row in data ]

def mysort(data,col,reverse_flag):
    data.sort(key=lambda x:x[col],reverse=reverse_flag)
    return data

def mymax(data):
    M = -1*float("inf")
    for i in range(len(data)):
        m = max(data[i])
        M = max(M,m)
    return M

def mymin(data):
    m = float("inf")
    for i in range(len(data)):
        M = min(data[i])
        m = min(m,M)
    return m

def myoutput(ls,space=True):
    if space:
        if len(ls)==0:
            print(" ")
        elif type(ls[0])==str:
            print(" ".join(ls))
        elif type(ls[0])==int:
            print(" ".join(map(str,ls)))
        else:
            print("Output Error")
    else:
        if len(ls)==0:
            print("")
        elif type(ls[0])==str:
            print("".join(ls))
        elif type(ls[0])==int:
            print("".join(map(str,ls)))
        else:
            print("Output Error")

H,N = myinput()
AB = mylistinput(N)

AB_sorted = mysort(AB,0,True)

maxA = AB[0][0]

HA = H+maxA


dp = [float("inf")]*(H+1)
dp[0] = 0

for i in range(1,H+1):
    for j in range(N):
        a = AB[j][0]
        b = AB[j][1]
        if i<a:
            dp[i] = min( dp[i], dp[0]+b )
        else:
            dp[i] = min( dp[i], dp[i-a]+b )

ans = dp[H]
print(ans)

Solution (Python):
H, N = map(int, input().split())
A, B = [], []
for i in range(N):
	a, b = map(int, input().split())
	A.append(a)
	B.append(b)


INF = 1 << 30
dp = [INF] * (H + 1) 
dp[0] = 0
for h in range(H + 1):
	for n in range(N):
		dp[h] = min(dp[h], B[n] + dp[max(h - A[n], 0)])

print(dp[H])

Solution (Python):
import numpy as np
h,n=map(int,input().split())
ab=np.array([list(map(int,input().split())) for _ in range(n)])
dp=np.zeros(10**4+1,np.int64) 
dp[0]=0
for a,b in ab:
      dp[1:a+1]=np.minimum(dp[1:a+1],b)


for i in range(1,h+1):
  dp[i]=np.min(dp[i-ab[:,0]]+ab[:,1])
print(dp[h])

Solution (Python):
h,n=map(int,input().split())
AB=[list(map(int,input().split())) for _ in range(n)]

DP=[float("inf")]*(h+max(AB)[0]+1)
DP[0]=0
for i in range(h+1):
    for a,b in AB:
        DP[i+a]=min(DP[i+a],DP[i]+b)

print(min(DP[h:]))

Solution (Python):
h,n=map(int,input().split())
a=[]
b=[]
for i in range(n):
    x,y=map(int,input().split())
    a.append(x)
    b.append(y)

cost=[float("inf")]*(h+1)
cost[0]=0
for i in range(1,h+1):
    for j in range(0,n):
        cost[i]=min(cost[i],cost[max(i-a[j],0)]+b[j])

print(cost[-1])

Solution (Python):
H, N = map(int, input().split())
magic = [list(map(int, input().split())) for _ in range(N)]

INF = 10**9
dp = [[INF for _ in range(H+10)] for _ in range(N+1)]

for i in range(1, N+1):
    a, b = magic[i-1]
    dp[i][0] = 0
    for j in range(1, H+1):
        dp[i][j] = min(dp[i][max(0, j-a)]+b, dp[i-1][j])

print(dp[N][H])

Solution (Python):
inf = 10**15
mod = 10**9+7
h,n = map(int, input().split())
ab = [list(map(int, input().split())) for i in range(n)]
dp = [[inf for j in range(h+1)] for i in range(n+1)]
for i in range(n):
    dp[i][0] = 0
    a,b = ab[i]
    for j in range(h):
        if j+1-a>=0:
            dp[i+1][j+1] = min(dp[i+1][j+1-a]+b, dp[i][j+1], dp[i][j+1-a]+b)
        else:
            dp[i+1][j+1] = min(dp[i][j+1], b)
print(dp[n][h])

Solution (Python):
h, n = (int(x) for x in input().split())
magic_list = []
for i in range(n):
    a, b = (int(x) for x in input().split())
    taple = (a,b)
    magic_list.append(taple)
ans = 0
mp=[]
for i in range(1,h+1):
    min_mp = 10000000000
    for j in range(n):
        if i<=magic_list[j][0]:
            use_mp = magic_list[j][1]    
        else:
            use_mp = mp[i-magic_list[j][0]-1]+magic_list[j][1]
        if use_mp<min_mp:
            min_mp = use_mp
    mp.append(min_mp)
    if i==h:
        ans=min_mp
print(ans)

Solution (Python):
import sys

input = sys.stdin.readline

INF = float("inf")


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

    dp = [INF] * (H + max(A))
    dp[0] = 0
    for h in range(H):
        for a, b in zip(A, B):
            if dp[h]+b < dp[h+a]:
                dp[h+a] = dp[h]+b
    ans = min(dp[H:])
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
H, N = map(int, input().split())
 
magic = [tuple(map(int, input().split())) for _ in range(N)]
 
DP = [0] * (H+10**4)
 
for h in range(1, H+1):
  DP[h] = min(DP[h - damage] + mp for damage, mp in magic)
print(DP[H])

Solution (Python):
h,n = 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 i in range(1,h+1):
    s = 100000000000
    for j in range(n):
        if i - a[j] < 0:
            s = min(s,b[j])
        else:
            s = min(s,dp[i-a[j]] + b[j])
    dp[i] = s
print(dp[h])

Solution (Python):
H, N = map(int, input().split())

magic = [tuple(map(int, input().split())) for _ in range(N)]

DP = [0] * (H+10**4)

for h in range(1, H+1):
  DP[h] = min(DP[h - damage] + mp for damage, mp in magic)
print(DP[H])

Solution (Python):
H, N = map(int, input().split())

magic = [tuple(map(int, input().split())) for _ in range(N)]

DP = [0] + [10**9]*H

for h in range(H):
  for damage, mp in magic:
    DP[min(h + damage, H)] = min(DP[min(h + damage, H)], DP[h] + mp)
print(DP[H])

Solution (Python):
H, N = map(int, input().split())
AB = [tuple(map(int, input().split())) for _ in range(N)]
dp = [0]
for h in range(H):
    dp.append(min([dp[max(0, h + 1 - A)] + B for A, B in AB]))
print(dp[-1])

Solution (Python):
h, n = map(int, input().split())


l = []
for i in range(n):
  a, b = map(int, input().split())
  l.append((a, b))
m = max(l, key=lambda x: x[0])[0]
dp = [9]*(h+m+1)
dp[0] = 0
for i in range(1, h+m+1):
  dp[i] = min([dp[i-l[j][0]]+l[j][1] for j in range(n)])
print(min(dp[h:h+m]))

Solution (Python):
H,N=map(int,input().split())

















dp = [float('inf')]*(H+1)
dp[0] = 0

for i in range(N):
    A_i,B_i = map(int,input().split())
    for j in range(H+1):
        nj = min(j+A_i,H)
        dp[nj] = min(dp[nj],dp[j] + B_i)

print(dp[H])

Solution (Python):
H,N = list(map(int,input().split()))
dp = [float("inf")] * (H+1)

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

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

print(dp[-1])

Solution (Python):
def main():
    import sys
    
    readlines = sys.stdin.readlines
    H, N = map(int, input().split())
    M = [tuple(map(int, s.split())) for s in readlines()]
    INF = 10 ** 9
    dp = [INF] * (H + 1)
    dp[0] = 0
    
    for i in range(N):
        a, b = M[i]
        for j in range(H):
            nj = min(H, j + a)
            dp[nj] = min(dp[nj], dp[j] + b)

    print(dp[H])


if __name__ == "__main__":
    main()

Solution (Python):
def main():
    import sys
    readline = sys.stdin.readline
    
    H, N = map(int, input().split())
    M = [tuple(map(int, readline().split())) for _ in range(N)]
    INF = 10 ** 9
    dp = [INF] * (H + 1)
    dp[0] = 0
    
    for i in range(N):
        a, b = M[i]
        for j in range(H):
            nj = min(H, j + a)
            dp[nj] = min(dp[nj], dp[j] + b)

    print(dp[H])


if __name__ == "__main__":
    main()

Solution (Python):
def main():
    import sys
    readline = sys.stdin.readline
    
    H, N = map(int, input().split())
    M = [tuple(map(int, readline().split())) for _ in range(N)]
    INF = float('inf')
    dp = [INF] * (H + 1)
    dp[0] = 0
    
    for i in range(N):
        a, b = M[i]
        for j in range(H):
            nj = min(H, j + a)
            dp[nj] = min(dp[nj], dp[j] + b)

    print(dp[H])


if __name__ == "__main__":
    main()

Solution (Python):
import sys
input = sys.stdin.readline
'''
n, m = map(int, input().split())
n = int(input())
A = list(map(int, input().split()))
S = input().strip()
for CASES in range(int(input())):
'''
inf = 100000000000000000  
mod = 998244353

'''


'''
H, n = map(int, input().split())
bas = 10**4
F = [inf] * (bas*3 + 10)
A = [0] * (bas + 10)
B = [0] * (bas + 10)
for i in range(1, n + 1):
    A[i], B[i] = map(int, input().split())
F[0]=0
for i in range(1, n + 1):
    for j in range(A[i], bas * 3 + 5):
        F[j] = min(F[j], F[j - A[i]] + B[i])
ans = inf
for i in range(H, bas * 3 + 5):
    ans = min(ans, F[i])
print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
'''
n, m = map(int, input().split())
n = int(input())
A = list(map(int, input().split()))
S = input().strip()
for CASES in range(int(input())):
'''
inf = 100000000000000000  
mod = 998244353

'''


'''
H, n = map(int, input().split())
bas = 10**4
F = [inf] * (bas*3 + 10)
A = [0] * (bas + 10)
B = [0] * (bas + 10)
for i in range(1, n + 1):
    A[i], B[i] = map(int, input().split())
F[0]=0
for i in range(1, n + 1):
    for j in range(A[i], bas * 3 + 5):
        F[j] = min(F[j], F[j - A[i]] + B[i])
ans = inf
for i in range(H, bas * 3 + 5):
    ans = min(ans, F[i])
print(ans)

Solution (Python):
import numpy as np
h, n = map(int,input().split())
a = np.zeros(n,dtype=int)
b = np.zeros(n,dtype=int)
for i in range(n):
    ai ,bi = map(int,input().split())
    a[i] = ai
    b[i] = bi

mh = np.zeros(10001,dtype=int)
for i in range(1,h+1):
    mh[i] = (mh[i-a]+b).min()

print(mh[h])

Solution (Python):
h,n=map(int,input().split())
l=[]
s=0
for i in range(n):
    a,b=map(int,input().split())
    s=max(s,a)
    l.append((a,b))
dp=[10**10]*(h+s)
dp[0]=0
for i in range(h):
    for s,t in l:
        dp[i+s]=min(dp[i]+t,dp[i+s])
print(min(dp[h:]))

Solution (Python):

H, N = map(int, input().split())
A, B = [], []
for _ in range(N):
    ai, bi = map(int, input().split())
    A.append(ai)
    B.append(bi)
maxA = max(A)


"""
DP[i] モンスターの体力をi減らすため消耗する魔力の最小値

答え min_{H <= i < H + maxAi} DP[i]
"""

INF = int(1e18)
DP = [INF for _ in range(H + maxA + 1)]
DP[0] = 0


for item in range(N):
    ai, bi = A[item], B[item]
    for idp, value in enumerate(DP):
        if value != INF and idp + ai < len(DP):
            DP[idp + ai] = min(DP[idp + ai], DP[idp] + bi)

ans = min(DP[H:H+maxA+1])
print(ans)

Solution (Python):
import sys
import math  
import bisect  
import queue  


def input():
    return sys.stdin.readline().rstrip()


def main():
    W, N = map(int, input().split())
    weight = []
    value = []
    for _ in range(N):
        A, B = map(int, input().split())
        weight.append(A)
        value.append(B)

    INF = 1000000007
    MAX_N = 1005
    MAX_W = 10005
    dp = [[INF for _ in range(MAX_W)] for _ in range(MAX_N)]
    for i in range(MAX_N):
        dp[i][0] = 0

    for i in range(N):
        for j in range(W + 1):
            dp[i + 1][j] = min(dp[i + 1][j], dp[i][j])
            w = j + weight[i]
            if w >= W:
                w = W
            dp[i + 1][w] = min(dp[i + 1][w], dp[i + 1][j] + value[i])

    print(dp[N][W])


if __name__ == '__main__':
    main()

Solution (Python):
h,n = map(int,input().split())
a = []
b = []
for _ in range(n):
  tmp = list(map(int,input().split()))
  a.append(tmp[0])
  b.append(tmp[1])

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

for i in range(n):
  for j in range(h+1):
    if j <= a[i]:
      dp[i+1][j] = min(dp[i][j],b[i])
    else:
      dp[i+1][j] = min(dp[i][j],dp[i+1][j-a[i]]+b[i])

print(dp[n][h])

Solution (Python):
import sys
input = sys.stdin.readline

H, N = map(int, input().split())
l = [tuple(map(int, input().split())) for _ in range(N)]
M = max([A for A, B in l])

dp = [0]*(H+M)
for i in range(1, H+M):
  dp[i] = min([B + dp[i-A] for A, B in l if i>=A]+[10**8])
ans = min([dp[i] for i in range(H, H+M)])
print(ans)

Solution (Python):
h, n = map(int, input().split())
a = []
b = []
for i in range(n):
  x, y = map(int, input().split())
  a.append(x)
  b.append(y)

dp = list([9e9] * (h + 1) for i in range(n + 1))
dp[0][0] = 0

for i in range(n):
  for j in range(h + 1):
    dp[i + 1][j] = min(dp[i+1][j], dp[i][j])
    dp[i+1][min(j+a[i], h)] = min(dp[i+1][min(j+a[i], h)], dp[i+1][j] + b[i])

print(dp[n][h])

Solution (Python):
H,N =map(int, input().split())
a = [] 
M = 0 
for i in range(N):
	t = list(map(int, input().split()))
	a.append(t)
	M = max(M,t[0])
dp = [100000000]*(H+1+M)
dp[0] = 0
for i in range(H):
	for j,k in a:
		dp[i+j] = min(dp[i+j],dp[i]+k)

print(min(dp[H:]))

Solution (Python):
import sys
input=sys.stdin.buffer.readline
H,N = map(int,input().split())
ab = [list(map(int,input().split())) for _ in range(N)]
dp = [10000000000]*(H+1)
dp[0] = 0
for i in range(1,H+1):
    for j in range(N):
        A = ab[j][0]
        B = ab[j][1]
        if i - A < 0:
            dp[i] = min(dp[i],dp[0]+B)
        else:
            dp[i] = min(dp[i],dp[i-A]+B)
print(dp[H])

Solution (Python):
H ,N = [int(i) for i in input().split()]
AB = []
for _ in range(N):
    AB.append([int(i) for i in input().split(' ')])

M = max(A for A, B in AB)

DP = [0] * (H+M)

for i in range(1,H+1):
    DP[i] = min(DP[i-a]+b for a,b in AB)

print(DP[H])

Solution (Python):
h, n = map(int, input().split())
a, b = [], []
for _ in range(n):
    i, j = map(int, input().split())
    a.append(i)
    b.append(j)


l = [0]
for i in range(1,h+1):
    cand = []
    for j in range(n):
        if i - a[j] >= 0 and l[i - a[j]] != 'none':
            cand.append(l[i - a[j]] + b[j])
    if cand == []:
        l.append('none')
    else:
        l.append(min(cand))
for i in range(h+1, h+max(a)):
    cand = []
    for j in range(n):
        if 0 <= i - a[j] < h and l[i - a[j]] != 'none':
            cand.append(l[i - a[j]] + b[j])
    if cand == []:
        l.append('none')
    else:
        l.append(min(cand))
l = l[h:]
l = [i for i in l if type(i) == int]
print(min(l))

Solution (Python):
H ,N = [int(i) for i in input().split()]
AB = []
for _ in range(N):
    AB.append([int(i) for i in input().split(' ')])
 
MAX = 0
for a, b in AB:
    MAX = a if MAX < a else MAX
 
DP = [10**10] * (H+MAX)
DP[0] = 0
for i in range(H):
    for a,b in AB:
        if DP[i] != 10**10:
            DP[i+a] = min(DP[i+a],DP[i] + b)
 
print(min(DP[H:]))

Solution (Python):
h,n=map(int,input().split())
a,b=[],[]
for i in range(n):
  aa,bb=map(int,input().split())
  a.append(aa)
  b.append(bb)
inf=float("inf")
dp=[[inf]*(h+1) for i in range(n+1)]
dp[0][0]=0
for i in range(n):
  for j in range(h+1):
    dp[i+1][j]=min(dp[i+1][j],dp[i][j])
    dp[i+1][min(h,j+a[i])]=min(dp[i+1][j]+b[i],dp[i+1][min(h,j+a[i])])
    
print(dp[n][h])

Solution (Python):
import sys
input = sys.stdin.readline

H, N = map(int, input().split())
S = [list(map(int, input().split())) for _ in range(N)]

INFTY = 10**8
dp = [INFTY]*(H+1)
dp[0] = 0

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

print(dp[H])

Solution (Python):
f=lambda:map(int,input().split())
h,n=f()
dp=[0]+[10**9]*h
for i in range(n):
  a,b=f()
  for j in range(h+1): dp[j]=min(dp[j],dp[max(j-a,0)]+b)
print(dp[h])

Solution (Python):
import sys
f=lambda:map(int,sys.stdin.readline().split())
h,n=f()
dp=[10**9]*(h+1)
dp[0]=0
for i in range(n):
  a,b=f()
  for j in range(h+1):
    dp[j]=min(dp[j],dp[max(j-a,0)]+b)
print(dp[h])

Solution (Python):
import sys
f=lambda:map(int,sys.stdin.readline().split())
h,n=f()
INF=10**9
dp=[[INF]*(h+1) for _ in range(n+1)]
dp[0][0]=0
for i in range(n):
  a,b=f()
  for j in range(h+1):
    dp[i+1][j]=min(dp[i][j],dp[i+1][max(j-a,0)]+b)
print(dp[n][h])

Solution (Python):
H, N = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N)]

dp = [[100000000]*(10000*2)]*(N+1)
dp[0][0] = 0

for i in range(0, N):
    for h in range(0, H+1):
        dp[i+1][h] = min(dp[i+1][h], dp[i][h])
        dp[i+1][min(h+AB[i][0], H)] = min(dp[i+1][min(h+AB[i][0], H)], dp[i+1][h]+AB[i][1])

ans = {}
for i in range(N):
    ans[i] = dp[i][H]
print(min(ans.values()))

Solution (Python):
def main():
    H, N = map(int, input().split())
    AB = [[]*2]*N
    for i in range(N):
        AB[i] = list(map(int, input().split()))

    dp = [[100000000]*(10000*2)]*(N+1)
    dp[0][0] = 0

    for i in range(0, N):
        for h in range(0, H+1):
            dp[i+1][h] = min(dp[i+1][h], dp[i][h])
            dp[i+1][min(h+AB[i][0], H)] = min(dp[i+1][min(h+AB[i][0], H)], dp[i+1][h]+AB[i][1])

    ans = {}
    for i in range(N):
        ans[i] = dp[i][H]
    print(min(ans.values()))

if __name__ == "__main__":
    main()

Solution (Python):
def main():
    H, N = map(int, input().split())
    AB = [list(map(int, input().split())) for _ in range(N)]

    dp = [[100000000]*(10000*2)]*(N+1)
    dp[0][0] = 0

    for i in range(0, N):
        for h in range(0, H+1):
            dp[i+1][h] = min(dp[i+1][h], dp[i][h])
            dp[i+1][min(h+AB[i][0], H)] = min(dp[i+1][min(h+AB[i][0], H)], dp[i+1][h]+AB[i][1])

    ans = {}
    for i in range(N):
        ans[i] = dp[i][H]
    print(min(ans.values()))
    
if __name__ == "__main__":
    main()

Solution (Python):
h, n = map(int,input().split())
AB = [list(map(int,input().split())) for _ in range(n)]
m = max(A for A, B in AB)
dp = [0]*(h+m)

for i in range(1, h+1):
    dp[i] = min(dp[i-A]+B for A,B in AB)

print(dp[h])