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

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

print(dp[-1])

Solution (Python):
h,n = map(int,input().split())
a_list = []
b_list = []
for i in range(n):
    a, b = map(int, input().split())
    a_list.append(a)
    b_list.append(b)
    
dp=[[float('inf') for i in range(h+1)]for i in range(n+1)]
dp[0][0]=0

for i in range(1,n+1):
  for j in range(h+1):
    if j>=a_list[i-1]:
      ai=a_list[i-1]
      bi=b_list[i-1]
      dp[i][j]=min(dp[i][j-ai]+bi,dp[i-1][j])
    else:
      dp[i][j]=min(dp[i-1][j],b_list[i-1])
ans=dp[n][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+=[a]
  B+=[b]
dp=[[float('inf') for i in range(H+1)]for i in range(N+1)]
dp[0][0]=0
for i in range(1,N+1):
  for j in range(H+1):
    if j>=A[i-1]:
      Ai=A[i-1]
      Bi=B[i-1]
      dp[i][j]=min(dp[i][j-Ai]+Bi,dp[i-1][j])
    else:
      dp[i][j]=min(dp[i-1][j],B[i-1])
ans=dp[N][H]
print(ans)

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

dp = [[10**10 for i in range(h+1)] for j in range(n+1)]
dp[0][0] = 0

for i in range(n):
    dmg=s[i][0]
    mp=s[i][1]
    for j in range(h+1):
        dp[i+1][j] = min(dp[i+1][j],dp[i][j])
        dp[i+1][min(j+dmg,h)] = min(dp[i+1][min(j+dmg,h)], dp[i+1][j]+mp)

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

Solution (Python):
from math import ceil
H,N = list(map(int, input().split()))
A = []
for _ in range(N):
  A.append(list(map(int, input().split())))
  




dp = [1e9] * (10010)
dp[0] = 0
for i in range(1,H+1):
  for a in A:
    ap, mp = a
    down = max(0, i - ap)
    dp[i] = min(dp[i], dp[down] + mp)
      
print(min(dp[H:]))

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=[[10**9 for i in range(H+1)] for j 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(H,j+A[i])],dp[i+1][j]+B[i])
print(dp[-1][-1])

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


  attack_max = np.max(a)
  majik_min = min(b)
  dp = np.zeros(h+attack_max,np.int)

  for i in range(1,len(dp)):
      c = dp[i-a[i-a>=0]]
      e = i-a[i-a>=0]
      d = c[(c!=0)+(e==0)]+b[i-a>=0][(c!=0)+(e==0)]
      if len(d)>0:
          dp[i] = np.min(d)

  print(np.min(dp[h:][dp[h:]>0]))
  
calc()

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

attack_max = np.max(a)
majik_min = min(b)
dp = np.zeros(h+attack_max,np.int)

for i in range(1,len(dp)):
    c = dp[i-a[i-a>=0]]
    e = i-a[i-a>=0]
    d = c[(c!=0)+(e==0)]+b[i-a>=0][(c!=0)+(e==0)]
    if len(d)>0:
        dp[i] = np.min(d)
    
print(np.min(dp[h:][dp[h:]>0]))

Solution (Python):
h,n=map(int,input().split())
AB=[]
maA=0
inf=float("inf")
for i in range(n):
   a,b=map(int,input().split())
   maA=max(maA,a)
   AB.append((a,b))

dp=[inf]*(h+maA+1)
dp[0]=0
for i in range(h+1):
   for aj,bj in AB:
      dp[i+aj]=min(dp[i+aj],dp[i]+bj)
print(min(dp[h:]))

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7 
input=lambda:sys.stdin.readline().rstrip()
def resolve():
    h, n = map(int, input().split())
    AB = [tuple(map(int, input().split())) for _ in range(n)]

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

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

    print(dp[-1])
resolve()

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

def main():
    H,N = map(int,input().split())
    x = []
    ma = 0
    for _ in range(N):
        a,b = map(int,input().split())
        ma = max(ma,a)
        x.append((a,b))
    INF = 10**18
    
    dp = [INF for _ in range(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 x)
    
    print(min(dp[H:]))

if __name__ == "__main__":
    main()

Solution (Python):
import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

H, N = lr()
U = 20000 
INF = 10 ** 8
dp = np.full(U, INF, np.int64)
dp[0] = 0
for i in range(N):
    a, b = lr()
    n = (U + (-U)%a)
    
    dp = np.resize(dp, n).reshape(-1, a)
    dp -= (np.arange(n//a) * b)[:, None]
    dp = np.minimum.accumulate(dp, axis=0)
    dp += (np.arange(n//a) * b)[:, None]
    dp = np.ravel(dp)[:U]

print(min(dp[H:]))

Solution (Python):
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 = [10 ** 18 for _ in range(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 ab)
print(min(dp[h:]))

Solution (Python):
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 = [10 ** 18 for _ in range(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 ab)
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) for _ in range(N+1)]
dp[0][0] = 0

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

print(dp[N][H])
"""



dp = [float("inf")]*(H+10**4)
dp[0] = 0
for i in range(N):
    for j in range(H):
        dp[j+A[i]] = min(dp[j+A[i]], dp[j]+B[i])

ans = float("inf")
for j in range(H, H+10**4):
    ans = min(ans, dp[j])

print(ans)

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 _ in range(N+1)]
dp[0][0] = 0

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

print(dp[N][H])

Solution (Python):
h, n = map(int,input().split())
lst = [list(map(int,input().split())) for _ in range(n)]
max_a = max(a for a, _ in lst )
dp = [10**18 for _ in range(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 lst)
print(min(dp[h:]))

Solution (Python):
import math

DP_MAX = 2*10**4 + 1
INF = 2*10**8

H,N = map(int,input().split())
M = [0]*N
for _ in range(N):
    M[_] = tuple(map(int,input().split()))

DP = [0]+[INF]*(DP_MAX - 1)

for A,B in M:
    for j in range(1,DP_MAX):
        if j - A >= 0:
            DP[j] = min(DP[j],DP[j - A]+B)

print(min(DP[H:]))

Solution (Python):
import itertools
from collections import deque,defaultdict,Counter
from itertools import accumulate
import bisect
from heapq import heappop,heappush,heapify
from fractions import gcd
from copy import deepcopy
import math
import queue


Mod = 1000000007
import sys
sys.setrecursionlimit(1000000) 
  
def sieve_of_eratosthenes(n):
    if not isinstance(n,int):
        raise TypeError("n is not int")
    if n<2:
        raise ValueError("n is not effective")
    prime = [1]*(n+1)
    for i in range(2,int(math.sqrt(n))+1):
        if prime[i] == 1:
            for j in range(2*i,n+1):
                if j%i == 0:
                    prime[j] = 0
    res = []
    for i in range(2,n+1):
        if prime[i] == 1:
            res.append(i)
    return res

def factorial(i):
    if i == 1:
        return 1
    else:
        return i*factorial(i-1)
 
class UnionFind:
    def __init__(self,n):
        self.parent = [i for i in range(n+1)]
        self.rank = [0 for i in range(n+1)]
    
    def findroot(self,x):
        if x == self.parent[x]:
            return x
        else:
            y = self.parent[x]
            y = self.findroot(self.parent[x])
            return y
    
    def union(self,x,y):
        px = self.findroot(x)
        py = self.findroot(y)
        if px < py:
            self.parent[py] = px
        else:
            self.parent[px] = py
 
    def same_group_or_no(self,x,y):
        return self.findroot(x) == self.findroot(y)




def main(): 
    h,n = map(int,input().split())
    ab = [list(map(int,input().split())) for i in range(n)]
    a = [ab[i][0] for i in range(n)]
    b = [ab[i][1] for i in range(n)]
    inf = float("inf")
    dp = [inf for i in range(h+max(a)+1)] 
    dp[0] = 0
    for i in range(n):
        for j in range(h+1):
            dp[j+a[i]] = min(dp[j]+b[i],dp[j+a[i]])

    print(min(dp[h:]))
if __name__ == "__main__":
    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())
ma = max(A)
dp = [0] * (H + ma)
dp[0] = 0
for i in range(N):
    a = A[i]
    b = B[i]
    for j in range(1, H + ma):
        if dp[j] == 0:
            dp[j] = dp[j - a] + b
        else:
            dp[j] = min(dp[j - a] + b, dp[j])
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())
ma = max(A)
dp = [float("inf")] * (H + ma)
dp[0] = 0
for i in range(N):
    a = A[i]
    b = B[i]
    for j in range(1, H + ma):
        dp[j] = min(dp[j - a] + b, dp[j])
print(min(dp[H:]))

Solution (Python):
import numpy as np
h, n = map(int, input().split())
a = [0 for i in range(10**4+1)]
b = [i for i in range(10**4+1)]
used = [False for i in range(10**4+1)]
for i in range(n):
    t = [int(i) for i in input().split(" ")] 
    if used[t[1]] == True:
        a[t[1]-1] = min(a[t[1]-1], t[0])
    else:
        a[t[1]] = t[0]
        used[t[1]] = True
a = np.array(a)[np.array(used)]
b = np.array(b)[np.array(used)]

dp = np.array([0 for i in range(h+1)])
for i in range(1, h+1):
    temp = i-a
    temp[temp<0] = 0
    dp[i] = np.min(dp[temp] + b)
print(dp[-1])

Solution (Python):
import math


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




dp=[[float("inf") for _ in range(h+1)] for _ in range(n)]
dp[0][0]=0
ma=list(map(int,input().split()))
for i in range(1,h+1):
    dp[0][i]=math.ceil(i/ma[0])*ma[1]

for i in range(1,n):
    ma=list(map(int,input().split()))
    
    for j in range(h+1):
        if j<ma[0]:
            cal=ma[1]
        else:
            
            cal=ma[1]+dp[i][j-ma[0]]
        
        dp[i][j]=min(dp[i-1][j],cal)
    


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

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

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

print(dp[H])

Solution (Python):
import sys

input = sys.stdin.readline
H, N = map(int, input().split())
magic = [list(map(int, input().split())) for _ in range(N)]

max_damage = max(damage for damage, cost in magic)
dp = [0] * (H + max_damage)

for x in range(1, H + max_damage):
    dp[x] = min(dp[x - damage] + cost for damage, cost in magic)

ans = min(dp[H:])

print(ans)

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 = [[10**10] * (H + 1) for _ in range(N+1)]

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

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

Solution (Python):
h,n=map(int,input().split())
A,B=[],[]
maA=0
for i in range(n):
   a,b=map(int,input().split())
   A.append(a)
   B.append(b)
   maA=max(maA,a)
inf=float("inf")
dp=[inf]*(h+maA+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):
H, N = map(int, input().split())

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

max_B = 0
for i in range(N):
  if skill_list[i][0] > max_B: max_B = skill_list[i][0]

dp = [float('inf') for i in range(H + max_B)]

dp[0] = 0
for i in range(H):
  for j in range(N):
    if dp[i + skill_list[j][0]] > dp[i] + skill_list[j][1]:
      dp[i + skill_list[j][0]] = dp[i] + skill_list[j][1]

print(min(dp[H : H + max_B]))

Solution (Python):
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 = [10 ** 18 for _ in range(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 ab)
print(min(dp[h:]))

Solution (Python):
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 = [10 ** 18 for _ in range(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 ab)
print(min(dp[h:]))

Solution (Python):
import sys
input = sys.stdin.buffer.readline
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getlist():
    return list(map(int, input().split()))
import math
import heapq
from collections import defaultdict, Counter, deque
MOD = 10**9 + 7
INF = 10**15


def main():
    h, k = getlist()
    mag = []
    for i in range(k):
        mag.append((getlist()))
    dp = [INF for i in range(h+1)]
    dp[0] = 0
    for i in range(h):
        cur = dp[i]
        for ma in mag:
            a, b = ma
            if i + a >= h:
                tgt = h
            else:
                tgt = i + a
            if dp[tgt] > cur + b:
                dp[tgt] = cur + b
    print(dp[-1])
    


if __name__ == '__main__':
    main()

"""
9999
3

2916
"""

Solution (Python):
h,n=map(int,input().split())
ab=[]
p=0
for i in range(n):
	a,b=map(int,input().split())
	p=max(p,a)
	ab.append([a,b])
dp=[[10**9]*(p+1+h) for _ in range(n+1)]
for i in range(n+1):
	dp[i][0]=0

for i in range(n):
	for j in range(p+h):
		if j+1-ab[i][0]>=0:
			dp[i+1][j+1]=min(dp[i][j+1],dp[i+1][j+1-ab[i][0]]+ab[i][1])
		else:
			dp[i+1][j+1]=dp[i][j+1]
ans=10**10
for i in range(h,h+p):
	ans=min(dp[n][i],ans)
print(ans)

Solution (Python):
h,n=map(int,input().split())
maA=0
inf=float("inf")
L=[]
for i in range(n):
   a,b=map(int,input().split())
   maA=max(maA,a)
   L.append((a,b))

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

Solution (Python):
h, n = map(int, input().split())
inf = 10**10
dp = [[inf for i in range(h+1)] for j in range(n+1)]

dp[0][0] = 0
for i in range(1,n+1):
    damage, cost = map(int, input().split())
    for j in range(h+1):
        if j - damage < 0:
            dp[i][j] = min(cost, dp[i][j], dp[i-1][j])
        else:
            dp[i][j] = min(dp[i][j - damage] + cost, dp[i-1][j])
print(dp[-1][h])

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

A = [0] * (N+1)
B = [0] * (N+1)


for i in range(1, N+1):
    A[i], B[i] = map(int, input().split())





INF = 100000010  




dp = [INF]*(H+1)

dp[0] = 0

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




print(dp[H])

Solution (Python):
h, n = (int(x) for x in input().split())
w = []
v = []
for _ in range(n):
    a, b = (int(x) for x in input().split())
    w.append(a)
    v.append(b)
dp = [[float('inf')] * (h) for _ in range(n + 1)]
for i in range(n):
    for j in range(h):
        if j < w[i]:
            dp[i + 1][j] = min(dp[i][j], v[i])
        else:
            dp[i + 1][j] = min(dp[i][j], dp[i + 1][j - w[i]] + v[i])
print(dp[n][h - 1])

Solution (Python):
h,n = map(int,input().split())
skills = []
for _ in range(n):
  a,b = map(int,input().split())
  skills.append((a,b))
dp = [float('inf') for _ in range(h+max(skills,key=lambda x:x[1])[1] + 1)]
dp[0] = 0
  
for i in range(len(dp)):
  if dp[i] ==float('inf'):
    continue
  for damage,mp in skills:
    if i+damage >= len(dp):
      continue
    if dp[i+damage] > dp[i] + mp:
      dp[i+damage] = dp[i]+mp
ans = min(filter(lambda x :x>0,dp[h:]))
print(ans)

Solution (Python):
def main():
  
  h,n=map(int,input().split())
  AB=tuple([list(map(int,input().split()))for _ in range(n)])
  
  DP=[float("inf") for _ in range(h+2)]
  DP[0]=0
  for i in range(1,h+2):
    for a,b in AB:
      if i<=a:
        DP[i]=min(DP[i],b)
      else:
        DP[i]=min(DP[i],DP[i-a]+b)
        
  print(DP[h])
  
if __name__=="__main__":
  main()

Solution (Python):
x=input().split()
h=int(x[0])
n=int(x[1])
import numpy as np
a=np.full(n,0,int)
b=np.full(n,0,int)
for k in range(n):
  x=input().split()
  a[k]=int(x[0])
  b[k]=int(x[1])
m=max(a)  
inf=10**8
dp=np.full(h+m+1,inf,int)
dp[0]=0
for k in range(1,h+m):
  dp[k]=(dp[k-a]+b).min()
print(dp[h:h+m].min())

Solution (Python):
x=input().split()
h=int(x[0])
n=int(x[1])
import numpy as np
a=np.full(n,0,int)
b=np.full(n,0,int)
for k in range(n):
  x=input().split()
  a[k]=int(x[0])
  b[k]=int(x[1])
m=max(a)  
inf=10**8
dp=np.full(h+m,inf,int)
dp[0]=0
for k in range(1,h+m):
  dp[k]=(dp[k-a]+b).min()
print(dp[h:h+m].min())

Solution (Python):
h,n=map(int,input().split())
ab=[]
for _ in range(n):
    ab.append(list(map(int,input().split())))
max_a=max([a for a,b in ab])
dp=[0 for _ in range(h+max_a)]

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

Solution (Python):










import numpy as np

h, n = map(int, input().split())
inf=2*10**9
a = np.full(n,inf, int)
b = np.full(n,inf, int)
for i in range(0, n):
  a[i], b[i] = map(int, input().split())

dp=np.full(10001,0,int)
dp[0]=0

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

print(dp[h])

Solution (Python):


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

dp = [[10**18 for i in range(h+1)] for j in range(n)]

for i in range(n):
    dp[i][0] = 0
    
for i in range(1,h+1):
    dp[0][i] = ((i+ab[0][0]-1) // ab[0][0]) * ab[0][1]

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

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

Solution (Python):
import sys
import numpy as np

h, n = map(int, input().split())
ab = np.array(sys.stdin.read().split(), dtype=np.int64)
aaa = ab[0::2]
bbb = ab[1::2]

dp = np.zeros(10001, dtype=np.int64)
for i in range(1, h + 1):
    dp[i] = (dp[i - aaa] + bbb).min()
print(dp[h])

Solution (Python):
import sys
inf = sys.maxsize

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

dp = [inf for _ in range(h + max([a[i] for i in range(n)]) + 10)] 
dp[0] = 0

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


print(min(dp[h:]))

Solution (Python):
h,n=map(int,input().split())
arr=[]
for _ in range(n):
  arr.append(list(map(int,input().split())))
dp=[10**10]*20001
dp[0]=0
for i in range(20001):
  for j in range(n):
    if i+arr[j][0]>20000:
      continue
    dp[i+arr[j][0]]=min(dp[i+arr[j][0]],dp[i]+arr[j][1])
ans=10**18
for i in range(h,20001):
  ans=min(ans,dp[i])
print(ans)

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

ab = []
for i in range(n):
  a, b = map(int, input().split())
  ab.append([a, b])

h_map = [-1 for _ in range(h+1)]

h_map[h] = 0
for i in range(h):
  i_map = h - i
  if h_map[i_map] == -1:
    continue
  
  for a, b in ab:
    if (i_map - a) <= 0:
      if h_map[0] != -1:
        h_map[0] = min(h_map[0], h_map[i_map]+b)
      else:
        h_map[0] = h_map[i_map] + b
    else:
      if h_map[i_map - a] != -1:
        h_map[i_map - a] = min(h_map[i_map - a], h_map[i_map]+b)
      else:
        h_map[i_map - a] = h_map[i_map]+b

print(h_map[0])

Solution (Python):
from fractions import gcd


import heapq
import math
from collections import defaultdict, Counter, deque
from bisect import *
import itertools
import fractions
import sys
sys.setrecursionlimit(10 ** 7)
MOD = 10 ** 9 + 7



def lcm(a, b):
    return a * b / fractions.gcd(a, b)


def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    
    return divisors


def factorize(n):
    fct = []  
    b, e = 2, 0  
    while b * b <= n:
        while n % b == 0:
            n = n // b
            e = e + 1
        if e > 0:
            fct.append((b, e))
        b, e = b + 1, 0
    if n > 1:
        fct.append((n, 1))
    return fct


def is_prime(n):
    if n == 1:
        return False

    for k in range(2, int(math.sqrt(n)) + 1):
        if n % k == 0:
            return False

    return True


def primes(n):
    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
    return [i for i in range(n + 1) if is_prime[i]]

def modpow(a, n, mod):
    res = 1
    while n > 0:
        if n & 1:
            res = res * a % mod
        a = a * a % mod
        n >>= 1
    return res


def modinv(a, mod):
    return modpow(a, mod - 2, mod)


def cnk(a, b):
    MOD = 10**9+7
    ret = 1
    for i in range(b):
        ret *= (a-i)
        ret %= MOD
        ret = ret * modinv(i+1, MOD) % MOD
    return ret


class UnionFind:
    def __init__(self, n):
        self.sz = [-1 for i in range(n)]

    
    def find(self, x):
        if self.sz[x] < 0:
            return x
        else:
            self.sz[x] = self.find(self.sz[x])
            return self.sz[x]

    
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return False
        if self.sz[x] > self.sz[y]:
            x, y = y, x
        self.sz[x] += self.sz[y]
        self.sz[y] = x

    
    def same(self, x, y):
        return self.find(x) == self.find(y)

    
    def size(self, x):
        return -self.sz[self.find(x)]


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


            
    
    




            


    




    


if __name__ == '__main__':
    main()

Solution (Python):
H,N = [int(zz) for zz in input().split()]
mahou = [[int(zz) for zz in input().split()] for _ in range(N)]

dmg = [i[0] for i in mahou]
mp = [i[1] for i in mahou]

dp = [[0]*(H+1) for _ in range(N)]
for j in range(1,H+1):
    if j <= dmg[0]:
        dp[0][j] = mp[0]
    else:
        dp[0][j] = dp[0][j-dmg[0]]+mp[0]

for i in range(1,N):
    for j in range(1,H+1):
        if j <= dmg[i]:
            dp[i][j] = min(mp[i],dp[i-1][j])
        else:
            dp[i][j] = min(dp[i][j-dmg[i]]+mp[i],dp[i-1][j])

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

Solution (Python):
import numpy as np
h, n = map(int, input().split())
a = np.zeros(n, int)
b = np.zeros(n, int)
for i in range(n):
    a[i], b[i] = map(int, input().split())
    
dp = np.zeros(h+1, int)
for i in range(1, h+1):
    rh = i - a
    rh[rh<0] = 0 
    dp[i] = np.min(dp[rh]+b)

print(dp[h])

Solution (Python):
w, h = (int(x) for x in input().split())
ab = []
for _ in range(h):
    a, b = (int(x) for x in input().split())
    ab.append([a, b])
 
dp = [10000000000000 for i in range(w+1)]
 
for j in range(w+1):
    for i in range(h):
        if j <= ab[i][0]:
            dp[j] = min(dp[j], ab[i][1])
        else:
            dp[j] = min(dp[j], dp[j-ab[i][0]]+ab[i][1])
 
print(dp[w])

Solution (Python):

from sys import stdin
from copy import deepcopy
from functools import reduce
from fractions import gcd
import math
import itertools
from collections import Counter
from itertools import chain  
from heapq import heappush, heappop

"""
N = int(input())
A, B = map(int,input().split())
A = list(map(int,input().split())) 
A = [int(input()) for _ in range(N)] 
lst = [list(map(int,input().split())) for i in range(M)] 
"""



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

inf = float("inf")
dp = [inf for i 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(i - AB[j][0], 0)] + AB[j][1])
    
print(dp[H])

Solution (Python):
import math
import fractions
import bisect
import collections
import itertools
import heapq
import string
import sys
import copy
from collections import deque
sys.setrecursionlimit(10**7)
MOD = 10**9+7
def gcd(a,b):return fractions.gcd(a,b) 
def lcm(a,b):return (a*b) // fractions.gcd(a,b) 
def iin(): return int(input()) 
def ifn(): return float(input()) 
def isn(): return input().split() 
def imn(): return map(int, input().split()) 
def fmn(): return map(float, input().split()) 
def iln(): return list(map(int, input().split())) 
def iln_s(): return sorted(iln()) 
def iln_r(): return sorted(iln(), reverse=True) 
def fln(): return list(map(float, input().split())) 
def join(l, s=''): return s.join(l) 
def perm(l, n): return itertools.permutations(l, n) 
def perm_count(n, r): return math.factorial(n) // math.factorial(n-r) 
def comb(l, n): return itertools.combinations(l, n) 
def comb_count(n, r): return math.factorial(n) // (math.factorial(n-r) * math.factorial(r)) 
def two_distance(a, b, c, d): return ((c-a)**2 + (d-b)**2)**.5 
def m_add(a,b): return (a+b) % MOD

H,N = imn()
AB = [iln() for _ in range(N)]

DP = [10 ** 10 for _ in range(10**4*2)]
DP[0] = 0
for i in range(N):
    for j in range(10**4*2):
        if j - AB[i][0] >= 0:
            DP[j] = min(DP[j], DP[j-AB[i][0]] + AB[i][1])
ans = 10**10
for i in range(H, 10**4*2):
    ans = min(ans, DP[i])
print(ans)

Solution (Python):
import math
H, N = list(map(int, input().split()))
 
AB = [list(map(int, input().split())) for _ in range(N)]
 
dp = [float('inf')] *(H+1)
dp[H] = 0
for a,b in AB:
    for i in range(H,-1,-1):
        if i <= H - a:
            dp[i] = min(dp[i], dp[i+a] + b)
    dp[0] = min(dp[0], min(dp[:a+1]) + b) 
print(dp[0])

Solution (Python):
def solve():
    N, M = map(int, input().split())
    INF = 10 ** 9
    dp = [INF] * (10 ** 7)
    dp[0] = 0

    for _ in range(M):
        a, b = list(map(int, input().split()))
        for i in range(N + 1):
            if dp[i] == INF:
                continue
            dp[i+a] = min(dp[i+a], dp[i] + b)
    return min(dp[N:])

print(solve())

Solution (Python):
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 = [10 ** 18 for _ in range(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 ab)
print(min(dp[h:]))

Solution (Python):
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 = [10 ** 18 for _ in range(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 ab)
print(min(dp[h:]))

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

for i in range(1,h+1):
    magic = 10 ** 10
    for j in range(n):
        magic = min(DP[max(0, i-A[j])] + B[j], magic)
    DP[i] = magic

print(DP[-1])

Solution (Python):
import sys
import math
import fractions
import bisect
sys.setrecursionlimit(4100000)

MOD = int(1e9+7)
PI = 3.14159265358979323846264338327950288
INF = 1e18

'''
1行のint
N, K = map(int, input().split())

1行のstring
S, T = input().split()

1行の整数配列
P = list(map(int,input().split()))

改行あり
x = []
y = []
for i in range(N):
    x1,y1=[int(i) for i in input().split()]
    x.append(x1)
    y.append(y1)

N行M列の初期化
dp = [[INF] * M for i in range(N)]

'''


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


dp = [[INF] * (H+10) for i in range(N)] 

for hp in range(H+10):
    dp[0][hp] = ((hp//A[0]) + int(hp%A[0] != 0))*B[0]

for magic in range(1, N):
    for hp in range(H+10):

        if hp-A[magic] >= 0:
            dp[magic][hp] = min(dp[magic-1][hp], dp[magic][hp-A[magic]] + B[magic])
        else:
            dp[magic][hp] = min(dp[magic-1][hp], B[magic])


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

Solution (Python):
h,n,*L=map(int,open(0).read().split())
dp=[0]*(h+10100)
for i in range(1,h+1):dp[i]=min(dp[i-a]+b for a,b in zip(*[iter(L)]*2))
print(dp[h])

Solution (Python):
h,n,*L=map(int,open(0).read().split())
dp=[float('inf')]*(h+10100)
dp[0]=0
for a,b in zip(*[iter(L)]*2):
    for i in range(h):
        t=dp[i]+b
        if t<dp[i+a]:
            dp[i+a]=dp[i]+b
print(min(dp[h:]))

Solution (Python):

import numpy as np
H, N = list(map(int, input().split()))
A = np.empty(N, int)
B = np.empty(N, int)
for i in range(N):
    A[i], B[i] = list(map(int, input().split()))


DP = np.empty(H+1, int)
DP[0] = 0
for i in range(1, H+1):
    I = i-A;
    I[I<0] = 0
    DP[i] = np.min(DP[I] + B)
    
print(DP[H])

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

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

A, B = zip(*AB)

dp = [-1 for _ in range(H+max(A))]
dp[0] = 0

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

print(dp[H])