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):
H, N = map(int, input().split())
ab = [list(map(int, input().split())) for i in range(N)]

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


for h in range(H):
    for a, b in ab:
        target = min(H, h + a)  
        dp[target] = min(dp[target], dp[h] + b)

print(dp[-1])

Solution (Python):
h,n = map(int,input().split())
mahou = []
for i in range(n):
	a,b = map(int,input().split())
	mahou.append((a,b))
dp = [10**18 for _ in range(h+1)]
dp[0] = 0
for i in range(h+1):
	for j, k in mahou:
		if j+i <= h:
			dp[j+i] = min(dp[i]+k, dp[j+i])
		else:
			dp[h] = min(dp[i]+k, dp[h])
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())
max_a=max(a)
dp=[float("inf")]*(h+max_a+1)
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:]))

Solution (Python):
from functools import lru_cache
import sys
sys.setrecursionlimit(10 ** 8)
h,n=map(int,input().split())
ab=[tuple(map(int,input().split())) for _ in range(n)]
ab.sort(key=lambda abi:(abi[1]/abi[0],abi[0]))

@lru_cache(maxsize=None)
def dp(i):
  if i<=0:
    return 0
  else:
    ans=float('inf')
    for a,b in ab:
      val=b+dp(i-a)
      if val<ans:
        ans=val
      else:
        break
    return ans

print(dp(h))

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

Solution (Python):
import heapq
H, N = map(int, input().split())
A = [] 
B = [] 
for i in range(N):
    ai, bi = map(int, input().split())
    A += [ai]
    B += [bi]
maxA = max(A)
dp = [[0 for j in range(H+maxA+1)]for i in range(N+1)]

for j in range(1, H+maxA+1):
    dp[0][j] = float('inf')

for i in range(N):
    for j in range(H+maxA+1):
        if j - A[i] < 0:
            dp[i+1][j] = dp[i][j]
        else:
            dp[i+1][j] = min(dp[i][j], dp[i+1][j-A[i]] + B[i])
ans = float('inf')
for j in range(H, H+maxA+1):
    ans = min(ans, dp[N][j])
print(ans)

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


dp = [[0] * (h+1) for _ in range(n+1)]
for j in range(1, h+1):
    dp[0][j] = float("inf")

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

print(dp[n][h])

Solution (Python):
H, N = map(int,input().split())
X = [list(map(int, input().split())) for i in range(N)]
X = sorted(X, key = lambda x:x[0])
DP = [float("inf")]*(H+X[-1][0]+X[-1][0])
DP[X[-1][0]-1] = 0
for i in range(X[-1][0], H+2*X[-1][0]):
    min = float("inf")
    for j in range(N):
        if min > DP[i-X[j][0]]+X[j][1]:
            min = DP[i-X[j][0]]+X[j][1]
        DP[i] = min

kouho = DP[H+X[-1][0]-1]
for i in range(X[-1][0]):
    if kouho > DP[H+X[-1][0]+i]:
        kouho = DP[H+X[-1][0]+i]
print(kouho)

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

dp = [10**8]*(2*10**4+1)
dp[0] = 0
for h in range(H+1):
    for ab in abl:
        a,b = ab
        dp[h+a] = min(dp[h+a], dp[h]+b)

print(min( dp[H:] ))

Solution (Python):
INF=10**30
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)
dp=[INF]*(H+10)
dp[0]=0
for i in range(N):
    for j in range(H+1):
        if(j<A[i]):
            dp[j]=min(dp[j],dp[0]+B[i])
        else:
            dp[j]=min(dp[j],dp[j-A[i]]+B[i])
print(dp[H])

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

ab = [list(map(int,input().split())) for i in range(n)]
ma = max(a for a,b in ab)


dp = [10**10]*(h+ma+1)
dp[0] = 0

for i in range(1,h+ma+1):
    dp[i] = min(dp[i-a]+b for a,b in ab)

print(min(dp[h:]))

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

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

for i in range(1,H+1):
    ans = inf
    for j in range(N):
        A = AB[j][0]
        B = AB[j][1]
        if i>=A:
            cand = dp[i-A]+B
        else:
            cand = B
        if cand<ans:
            ans=cand
    dp[i] = ans

print(dp[-1])

Solution (Python):
h,n=map(int,input().split())
lis=[]
amax=0
for i in range(n):
  a,b=map(int,input().split())
  if a>amax:
    amax=a
  lis.append([a,b])
dp=[0]*(h+amax)
for i in range(1,h+amax):
  dp[i]=min(dp[i-a]+b for a,b in lis)
print(dp[h])

Solution (Python):
h,n,*t = map(int,open(0).read().split())

dp = [0] + [10**8]* h

for a,b in  zip(*[iter(t)]*2):
    for life_point in range(h +1):
        
        original_life = max(0,life_point - a)

        magic_consum = dp[original_life]+ b

        dp[life_point] = min(dp[life_point],magic_consum)

print(dp[h])

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

dp = [[float('inf')] * (h+1) for _ 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())

ab = [list(map(int,input().split())) for i in range(n)]
ma = max(a for a,b in ab)


dp = [10**10]*(h+ma+1)
dp[0] = 0

for i in range(1,h+ma+1):
    dp[i] = min(dp[i-a]+b for a,b in ab)

print(min(dp[h:]))

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

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

dp = [10**10]*(H+1)
dp[0] = 0
for i in range(H):
    for ab in AB:
        a,b = ab[0], ab[1]
        idx = i+a if i+a < H else H
        dp[idx] = min(dp[idx], dp[i]+b)
print(dp[H])

Solution (Python):

H,N=map(int,input().split())
A=[0 for i in range(N)]
dp=[float("inf") for i in range(10**4+1)]
dp[0]=0
for i in range(N):
    a,b=map(int,input().split())
    A[i]=a
    for j in range(10**4+1):
        if j+a>10**4:
            break
        dp[j+a]=min(dp[j]+b,dp[j+a])


if H+max(A)>10**4:
    print(min(dp[H:]))
else:
    print(min(dp[H:H+max(A)]))

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

max_A = max(a for a,b in magics)
INF = 10**10
DP = [INF]*(H+max_A)
DP[0] = 0

for i in range(1,H+max_A):
    DP[i] = min(DP[i-a] + b for a,b in magics)
    
ans = min(DP[H:])
print(ans)

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

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

for i in range(1, H + 1):
    for j in range(N):
        dp[i] = min(dp[i], dp[max(0, i - A[j])] + B[j])
        
print(dp[H])

Solution (Python):
import numpy as np
H,N= map(int, input().split())
m = np.array([list(map(int, input().split())) for _ in range(N)])
max_a = np.max(m[:,0])
dp = np.zeros(H+max_a+1, dtype='i8')
for i in range(max_a+1, H+max_a+1):
    dp[i] = np.min(dp[i-m[:,0]] + m[:,1])
print(dp[H+max_a])

Solution (Python):
def main():
    H,N = [int(x) for x in input().split()]
    A,B = [],[]
    for _ in range(N):
        a,b = [int(x) for x in input().split()]
        A.append(a)
        B.append(b)

    dp = [float('inf')]*(H+1)
    dp[0] = 0
    for i in range(N):
        for j in range(H+1):
            
            dp[min(j+A[i],H)] = min(dp[min(j+A[i],H)], dp[j]+B[i])
            
    print(int(dp[H]))


if __name__ == '__main__':
    main()

Solution (Python):


def main():
    H,N = [int(x) for x in input().split()]
    A,B = [],[]
    for _ in range(N):
        a,b = [int(x) for x in input().split()]
        A.append(a)
        B.append(b)

    
    
    dp = [float('inf')]*(H+1)
    dp[0] = 0
    for i in range(N):
        for j in range(H+1):
            
            dp[min(j+A[i],H)] = min(dp[min(j+A[i],H)], dp[j]+B[i])
            
            
            
    print(int(dp[H]))


if __name__ == '__main__':
    main()

Solution (Python):








 

 

 

from sys import stdin


def main():
    input = stdin.readline
    
    h,n = map(int,input().split())
    
    ab= [list(map(int,input().split())) for _ in range(n)]
    
    dp = [[100000001 for _ in range(h+1)] for _ in range(n+1)]
    
    
    
    for i in range(1,n+1):
        dp[i][0] = 0
        for j in range(h+1):
            a = ab[i-1][0]
            b = ab[i-1][1]
            dp[i][j] = min(dp[i][j],dp[i-1][j])
            if j+a <= h:
                dp[i][j+a] = min(dp[i][j] + b, dp[i-1][j+a], dp[i][j+a])
            elif j+a > h:
                dp[i][h] = min(dp[i][j] + b, dp[i-1][h], dp[i][h])

    
    print(dp[-1][-1])

if __name__ == "__main__":
    main()

Solution (Python):








 

 

 

from sys import stdin


def main():
    input = stdin.readline
    
    h,n = map(int,input().split())
    
    ab= [list(map(int,input().split())) for _ in range(n)]
    
    dp = [[float("inf") for _ in range(h+1)] for _ in range(n+1)]
    
    
    
    for i in range(1,n+1):
        dp[i][0] = 0
        for j in range(h+1):
            a = ab[i-1][0]
            b = ab[i-1][1]
            dp[i][j] = min(dp[i][j],dp[i-1][j])
            if j+a <= h:
                dp[i][j+a] = min(dp[i][j] + b, dp[i-1][j+a], dp[i][j+a])
            elif j+a > h:
                dp[i][h] = min(dp[i][j] + b, dp[i-1][h], dp[i][h])

    
    print(dp[-1][-1])

if __name__ == "__main__":
    main()

Solution (Python):
import sys
sys.setrecursionlimit(10**9)

INF = 10**20
def main():
    H,N = map(int,input().split())
    A,B = [],[]
    for _ in range(N):
        a,b = map(int,input().split())
        A.append(a)
        B.append(b)

    tp = 3 * 10**4
    dp = [INF] * tp
    dp[0] = 0
    ans = INF
    for h in range(tp):
        minim = INF
        for i in range(N):
            dp_i = h-A[i]
            if dp_i >= 0 and dp[dp_i] != INF:
                minim = min(minim,dp[dp_i]+B[i])
                

        if minim != INF:
            dp[h] = minim
            if h >= H:
                ans = min(ans,dp[h])


    print(ans)


if __name__ == "__main__":
  main()

Solution (Python):





h,n=map(int,input().split())
a,b=[],[]
for i in range(n):
    a_sub,b_sub=map(int,input().split())
    a.append(a_sub)
    b.append(b_sub)
inf=10000000000000
ma=max(a)

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

for i in range(h+1+ma):
    if dp[i] == inf:
        continue
    for j in range(n):    
        ni = i + a[j] 
        if ni<h+ma:
            dp[ni] = min(dp[ni], dp[i] + b[j])        
print(min(dp[h:]))

Solution (Python):
h, n = map(int, input().split())
ab = []
for _ in range(n):
    ab.append(list(map(int, input().split())))
inf = 1001001001
lis = [inf] * (2*10**4+5)
lis[0] = 0
for i in range(len(lis)):
    for j in range(n):
        a = ab[j][0]
        b = ab[j][1]
        if i+a < len(lis):
            lis[i+a] = min(lis[i]+b, lis[i+a])
print(min(lis[h:]))

Solution (Python):

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

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



        
ldp=[[0 for j in range(h)]for i in range(n)]
for i in range(n):
    for j in range(h):
        if i==0:
            ldp[i][j]=-(-(j+1)//l[i][0])*l[i][1]
        else:
            if j>=l[i][0]:
                ldp[i][j]=min(ldp[i-1][j],ldp[i][j-l[i][0]]+l[i][1])
            else:
                ldp[i][j]=min(ldp[i-1][j],l[i][1])
print(ldp[-1][-1])

Solution (Python):

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

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


amax=0
for i in range(n):
    if amax<l[i][0]:
        amax=l[i][0]
        
ldp=[[0 for j in range(h+amax)]for i in range(n)]
for i in range(n):
    for j in range(h+amax):
        if i==0:
            ldp[i][j]=-(-(j+1)//l[i][0])*l[i][1]
        else:
            if j>=l[i][0]:
                ldp[i][j]=min(ldp[i-1][j],ldp[i][j-l[i][0]]+l[i][1])
            else:
                ldp[i][j]=min(ldp[i-1][j],l[i][1])
print(min(ldp[-1][h-1:]))

Solution (Python):
from collections import defaultdict
h,n=map(int,input().split())
INF=float('inf')
ab=defaultdict(lambda: -INF)
for _ in range(n):
  a,b=map(int,input().split())
  ab[b]=max(ab[b],a)
dp=[INF]*(h+max(ab.values())+1)
dp[0]=0
for i in range(1,ab[min(ab.keys())]+1):
  dp[i]=min(ab.keys())
for i in range(ab[min(ab.keys())]+1,h+max(ab.values())+1):
  for m,d in ab.items():
    if i>=d:
      dp[i]=min(dp[i],dp[i-d]+m)
print(min(dp[h:]))

Solution (Python):
import sys
from collections import defaultdict

readline = sys.stdin.buffer.readline


def geta(fn=lambda s: s.decode()):
    return map(fn, readline().split())


def gete(fn=lambda s: s.decode()):
    return fn(readline().rstrip())


sys.setrecursionlimit(10**5)


def main():
    h, n = geta(int)
    a, b = [0] * (n + 1), [0] * (n + 1)
    for i in range(n):
        a[i + 1], b[i + 1] = geta(int)

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

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

    print(dp[n][h])


if __name__ == "__main__":
    main()

Solution (Python):
[H,N]=[int(i) for i in input().split()]
A=[0 for i in range(N)]
B=[0 for i in range(N)]
for n in range(N):
  [A[n],B[n]]=[int(i) for i in input().split()]
k=H+max(A)+1
DP=[100000000 for i in range(k)]
DP[0]=0
for n in range(N):
  for h in range(k):
    if h-A[n]>-1:
    	if DP[h-A[n]]+B[n]<DP[h]:DP[h]=DP[h-A[n]]+B[n]
print(min(DP[H:]))

Solution (Python):
[h,n] = [int(i) for i in input().split()]
ab = []
for i in range(n):
    ab.append([int(j) for j in input().split()])
dp =[0] * 10001 + [10 ** 10] * 10000
for i in range(10001,20001):
    for ls in ab:
        dp[i] = min(dp[i],dp[i-ls[0]]+ls[1])
print(dp[10000+h])

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10**9 + 7

H, N = MAP()
A, B = [0]*N, [0]*N
for i in range(N):
	A[i], B[i] = MAP()


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


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):
def main():
    H,N = map(int, input().split())
    A,B = [0]*N,[0]*N
    for i in range(N): A[i],B[i]=map(int, input().split())
    
    INF = float('inf')
    dp = [INF]*(H+1)
    dp[0] = 0
    for h in range(1,H+1):
        
        for a,b in zip(A,B):
            if h-a>=0:
                dp[h]=min(dp[h],dp[h-a]+b)
            else:
                dp[h]=min(dp[h],b)
    print(dp[H])

main()

Solution (Python):
H,N = map(int,input().split())
INF = float('inf')

dp = [INF] * (H+1)

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

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

print(dp[-1])

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10**9 + 7

def main():
	H, N = MAP()
	A, B = [0]*N, [0]*N
	for i in range(N):
		A[i], B[i] = MAP()

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


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

	print(dp[H])

if __name__ == '__main__':
	main()

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10**9 + 7

def main():
	H, N = MAP()
	A, B = [0]*N, [0]*N
	for i in range(N):
		A[i], B[i] = MAP()

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


	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])
			if j>= A[i]:
				dp[i+1][j] = min(dp[i][j], dp[i+1][j-A[i]]+B[i])
			

	
	

	print(dp[N][H])

if __name__ == '__main__':
	main()

Solution (Python):
def dp(H, N, ab):
  max_a = max([ab[i][0] for i in range(N)])
  d = [INF for _ in range(H + max_a)]
  d[0] = 0
  for h in range(1, H + max_a):
    d[h] = min(d[h - a] + b for a, b in ab)
  return min(d[H:])
INF = 10 ** 10
H, N = map(int, input().split())
ab = [tuple(map(int, input().split())) for _ in range(N)]
print(dp(H, N, ab))

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import numpy as np

H,N = map(int,readline().split())
m = map(int,read().split())
AB = zip(m,m)

INF = 10 ** 18
U = 20000
dp = np.full(U, INF, np.int64)
dp[0] = 0

for a,b in AB:
    n = (U + (-U) % a) // a
    dp = np.resize(dp, U + (-U) % a).reshape(-1,a)
    dp -= (np.arange(n) * b)[:,None]
    dp = np.minimum.accumulate(dp, axis=0)
    dp += (np.arange(n) * b)[:,None]
    dp = dp.ravel()[:U]

answer = min(dp[H:])
print(answer)

Solution (Python):
from collections import Counter
from collections import deque
import math
import bisect
import sys
def input(): return sys.stdin.readline().strip()
def mp(): return map(int,input().split())
def lmp(): return list(map(int,input().split()))


h,n=mp()
magic=[lmp() for i in range(n)]
dp=[float("inf")]*(h+1)
dp[0]=0
for i in range(h):
    for k in range(n):
        ni=min(i+magic[k][0],h)
        dp[ni]=min(dp[ni],dp[i]+magic[k][1])
print(dp[-1])

Solution (Python):
H, N = map(int,input().split())
Magic = [list(map(int, input().split())) for i in range(N)]
MAX_COST = max(Magic)[1]

dp = [float('inf')] * (H + 1)
dp[0] = 0
for h in range(H):
    for damage, cost in Magic:
        next_index = min(h + damage, H)
        dp[next_index] = min(dp[next_index], dp[h] + cost)
 
print(dp[-1])

Solution (Python):
h, n = map(int, input().split())
magics = [list(map(int, input().split())) for _ in range(n)]
max_a = max(a for a, b in magics)
dp = [0] * (h + max_a)
for i in range(1, h + max_a):
    dp[i] = min(dp[i - a] + b for a, b in magics)
print(dp[h])

Solution (Python):
def main() -> None:
    H, N = rmi()
    AB = []
    for _ in range(N):
        AB.append(rmi())
    dp = [10 ** 9] * (H + 1)
    dp[0] = 0
    for damage, mp in AB:
        for i in range(len(dp)):
            prev = max(i - damage, 0)
            dp[i] = min(dp[i], dp[prev] + mp)
    w(dp[H])


def r() -> str:
    return input().strip()


def ri() -> int:
    return int(r())


def rmi(delim: str = ' ') -> tuple:
    return tuple(map(int, input().split(delim)))


def w(data) -> None:
    print(data)


def wm(*data, delim: str = ' ') -> None:
    print(delim.join(map(str, data)))


if __name__ == '__main__':
    main()

Solution (Python):
h,n = map(int,input().split())
len = h + 10005
inf = 1000000000
res = inf
dp = [inf] * len
dp[0] = 0
for i in range(n):
    a,b = map(int,input().split())
    for j in range(len):
        if j >= a:
            dp[j] = min(dp[j],dp[j-a] + b)
        if j >= h:
            res = min(res,dp[j])
print(res)

Solution (Python):
import sys
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7

def main():
    H, N = map(int, readline().split())
    Magic = list(list(map(int, readline().split())) for _ in range(N))

    dp = [INF]*(H+1)
    dp[0] = 0
    for h in range(H):
        for damage, cost in Magic:
            next_index = min(h + damage, H)
            dp[next_index] = min(dp[next_index],dp[h]+cost)
    print(dp[-1])

if __name__ == '__main__':
    main()

Solution (Python):
n, m = map(int, input().split())
dmg = []
cost = []

for i in range(m):
    a, b = map(int, input().split())
    dmg.append(a)
    cost.append(b)

inf = 10**9
dp = [inf] * 30000
dp[0] = 0

for i in range(m):
    for j in range(n):
        if dp[j] != inf:
            dp[j + dmg[i]] = min(dp[j + dmg[i]], dp[j] + cost[i])
print(min(dp[n:]))

Solution (Python):
import numpy as np

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

max_a = np.max(m[:,0])
dp = np.zeros(h+max_a+1, dtype='i8')
for i in range(max_a+1, h+max_a+1):
    dp[i] = np.min(dp[i-m[:,0]] + m[:,1])
print(dp[h+max_a])

Solution (Python):
from sys import maxsize

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

dp = [0] + [maxsize]*h
for a, b in m:
    for i in range(h+1):
        dp[min(i+a, h)] = min(dp[min(i+a, h)], dp[i]+b)
print(dp[h])

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

    inf = 10**18
    cost = [inf] * (H+1)
    cost[0] = 0
    for a, b in M:
        for i in range(1, H+1):
            tmp = cost[i-a] + b if i-a > 0 else b
            cost[i] = min(cost[i], tmp)
    print(cost[H])

abc153_e()

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

print(dp[h])

Solution (Python):
h, n = [int(x) for x in input().split()]
AB = [[int(x) for x in input().split()] for _ in range(n)]
h_max = 10 ** 4
inf = 10 ** 9
dp = [inf] * (h_max + 1)
dp[0] = 0
for h_target in range(1, h_max + 1):
    for attack, mp in AB:
        h_remain = max(0, h_target - attack)
        dp[h_target] = min(dp[h_target], dp[h_remain] + mp)
print(dp[h])

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 5 + 10)


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


def resolve():

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

    INF = 10**10  

    I, J = N, H
    
    dp = [[INF]*(J+1) for _ in range(I+1)]
    
    for i in range(I):
        dp[i][0] = 0
    
    for i in range(I):
        for j in range(J+1):

            dp[i+1][j] = min(dp[i+1][j], dp[i][j])
            dp[i+1][min(j+A[i], J)] = min(dp[i+1]
                                          [min(j+A[i], J)], dp[i+1][j]+B[i])

    print(dp[I][J])


resolve()

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 5 + 10)


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


def resolve():


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

    INF = 10**10  

    I, J = N, H
    
    dp = [[INF]*(J+1) for _ in range(I+1)]
    
    for i in range(I):
        dp[i][0] = 0
    
    for i in range(I):
        for j in range(J+1):
            dp[i+1][j] = min(dp[i+1][j], dp[i][j])
            dp[i+1][min(j+A[i],J)] = min(dp[i+1][min(j+A[i],J)], dp[i+1][j]+B[i])
            
            
    print(dp[I][J])


resolve()

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 5 + 10)


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


def resolve():

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

    INF = 10**10  

    I, J = N, H
    
    dp = [[INF]*(J+1) for _ in range(I+1)]
    
    for i in range(I):
        dp[i][0] = 0
    
    for i in range(I):
        for j in range(J+1):
            
            dp[i+1][j] = min(dp[i+1][j], dp[i][j])
            
            dp[i+1][min(j+A[i], J)] = min(dp[i+1][min(j+A[i], J)], dp[i+1][j]+B[i])
    print(dp[I][J])


resolve()

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_)
dp = [0] * (max(a) + h)
for i in range(1, max(a) + h):
    dp[i] = min(dp[i - a[j]] + b[j] for j in range(n))
print(min(dp[h:]))

Solution (Python):
hh,n = map(int,raw_input().split(' '))
spells = [map(int, raw_input().split(' ')) for _ in range(n)]
h = [+float('inf')] * (hh+1)
h[0] = 0
for health in range(1, hh+1):
	for u,v in spells: h[health] = min(h[health], h[max(0,health - u)] + v)

print h[hh]

Solution (Python):
hh,n = map(int,raw_input().split(' '))
spells = [map(int, raw_input().split(' ')) for _ in range(n)]
h = {}
h[0] = 0


for health in range(1, hh+1):
	for u,v in spells:
		h[health] = min(h[health] if health in h else +float('inf'), h[max(0,health - u)] + v)

print h[hh]

Solution (Python):
ni = lambda: int(input())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))

INF = 10**10

h,n = nm()

dp = [INF] * (h+1)

dp[0] = 0

for i in range(n):
  a,b = nm()

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

print(dp[h])

Solution (Python):
h, n  = map(int, input().split())
dp = [None] * (h+10)
dat = []
for _ in range(n):
    a,b = map(int, input().split())
    dat.append([a,b])
dp[0] = 0
for i in range(h):
    if dp[i] is None:
        continue
    for j in range(len(dat)):
        a,b = dat[j]
        
        magic = b + dp[i]
        nextdp = i + a
        if nextdp > h:
            nextdp = h
        if dp[nextdp] is None:
            dp[nextdp] = magic
        else:
            dp[nextdp] = min(dp[nextdp], magic)

print(dp[h])

Solution (Python):
h,n=map(int,input().split())
ab=[list(map(int,input().split()))for _ in range(n)]
maxa=max([a for a,b in ab])
maxmp=pow(10,8)
dp=[maxmp]*(h+maxa) 
dp[0]=0
for i in range(h+maxa):
  b=[dp[i-a]+b for a,b in ab if i-a>=0]
  dp[i]=min(dp[i],min(b)) if b else dp[i]
print(min(dp[h:]))

Solution (Python):
h,n=map(int,input().split())
ab=[list(map(int,input().split()))for _ in range(n)]
maxmp=pow(10,8)
dp=[maxmp]*(h+10000) 
dp[0]=0
for i in range(h+10000):
  b=[dp[i-a]+b for a,b in ab if i-a>=0]
  dp[i]=min(dp[i],min(b)) if b else dp[i]
print(min(dp[h:]))

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

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

for i in range(H):
    for a,b in magic:
        d=min(i+a,H)
        dp[d]=min(dp[d],dp[i]+b)
print(dp[H])

Solution (Python):
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()

from collections import defaultdict, deque, Counter
from sys import exit
import heapq
import math
import copy
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

H, N = getNM()
magic = []
for i in range(N):
    a, b = getNM()
    
    magic.append([a, b])

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

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

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

INF = 1e100

dp = [[INF] * (10 ** 4 + 1) for i in range(10 ** 3 + 1)]

dp[0][0] = 0

for i in range(n):
    a, b = map(int, input().split())
    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))] = min(dp[i+1][min(h, (j+a))], dp[i+1][j] + b)

print(dp[n][h])

Solution (Python):
import numpy as np
h, n = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(n)]
np_ab = np.array(ab)
max_a = max(np_ab[:,0]) 
dp = [0]*(h + max_a)

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

Solution (Python):
h, n = map(int, input().split())
magics = [list(map(int, input().split())) for _ in range(n)]
max_a = max(a for a, b in magics)
dp = [0] * (h + max_a)
for i in range(1, h + max_a):
    dp[i] = min(dp[i - a] + b for a, b in magics)
print(dp[h])

Solution (Python):
H,N=map(int,input().split())
AB=[]
for i in range(N):
    AB.append(list(map(int,input().split())))
maxA=max(AB)[0]

dp=[float("inf")]*(H+maxA)
dp[0]=0
for i in range(H):
    for fire,cost in AB:
        dp[i+fire]=min(dp[i+fire],dp[i]+cost)

ans=min(dp[H:])
print(ans)