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):
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
def input(): return sys.stdin.readline().rstrip()

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())
    dp=[[INF]*(10**4*3) for _ in range(N+1)]
    dp[0][0]=0
    ans=INF
    for i in range(N):
        for hp in range(H+10**4+10):
            if hp>=A[i]:
                dp[i+1][hp]=min(dp[i][hp],dp[i+1][hp])
                dp[i+1][hp]=min(dp[i+1][hp],dp[i][hp-A[i]]+B[i])
                dp[i+1][hp]=min(dp[i+1][hp],dp[i+1][hp-A[i]]+B[i])
            else:
                dp[i+1][hp]=min(dp[i][hp],dp[i+1][hp])
            if hp>=H:
                ans=min(ans,dp[i+1][hp])
    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
import sys, bisect, math, itertools, string, queue, copy


from collections import Counter,defaultdict,deque
from itertools import permutations, combinations
from heapq import heappop, heappush

sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(input()) 
def inpm(): return map(int,input().split()) 
def inpl(): return list(map(int, input().split())) 
def inpls(): return list(input().split())  
def inplm(n): return list(int(input()) for _ in range(n)) 
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return sorted([list(map(int, input().split())) for _ in range(n)]) 
def graph():
    n=inp()
    g=[[] for _ in range(n)]
    for i in range(n):
        a = inp()
        a -= 1
        g[i].append(a)
        g[a].append(i)
    return n,g

def Knapsack2(W,w,v,h): 
    n=len(w)
    v_max=max(v)+h+5
    
    dp=[0]+[float('inf') for _ in range(v_max+1)]
    for i in range(n):
        for j in range(0,v_max+1):
            if j >= v[i]:
                if j-v[i]>W:
                    continue
                dp[j]=min(dp[j],dp[j-v[i]]+w[i])
    ans = 10**10
    for i in range(h,v_max+1):
        ans = min(ans,dp[i])
        
    print(ans)

def main():
    h,n = inpm()
    a = []
    b = []
    for _ in range(n):
        a1,b1 = inpm()
        a.append(a1)
        b.append(b1)
    Knapsack2(h,b,a,h)

    
if __name__ == "__main__":
    main()

Solution (Python):
from math import ceil


INF = float('inf')
H, N = map(int, input().split())
AB = []
for i in range(N):
    a, b = map(int, input().split())
    AB.append((a, b))

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

for i in range(N):
    a, b = AB[i]
    for j in range(1, ceil(H/a)+1):
        s = 1 + (j-1) * a
        t = min(H, s + a - 1)
        for k in range(s, t+1):
            dp[k] = min(dp[k], dp[max(0, k-a)] + b)


print(dp[H])

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

INF = 10**9
dp = [[INF] * (h+1) for _ in range(n+1)]
dp[0][h] = 0
for i in range(n):
    for j in reversed(range(h+1)):
        a, b = M[i]
        if j > h - a:
            dp[i+1][j] = min(dp[i][j], b)
        else:
            dp[i+1][j] = min(dp[i][j], dp[i+1][j+a] + b)
print(dp[n][0])

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

dp = [float("inf")]*H + [0]
ans = float("inf")
for j in reversed(range(H+1)):
    for i in range(N):
        if dp[j] < float("inf"):
            if j - AB[i][0] >= 0:
                dp[j - AB[i][0]] = min(dp[j - AB[i][0]], dp[j] + AB[i][1])
            else:
                ans = min(ans, dp[j] + AB[i][1])

print(min(dp[0], ans))

Solution (Python):
def main():
  import sys
  input = sys.stdin.readline
  
  H,N = map(int,input().split())
  AB = [tuple(map(int,input().split())) for _ in range(N)]

  dp = [[float('inf') for _ in range(H+1)] for _ in range(N+1)]
  dp[0][0] = 0

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

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

if __name__ == '__main__':
  main()

Solution (Python):
h,n=map(int,input().split())
p=[float("INF")]*(h+1)
p[0]=0
for i in range(n):
    a,b=map(int,input().split())
    for j in range(h+1):
        if p[min(h,j+a)]>p[j]+b:
            p[min(j+a,h)]=p[j]+b
print(p[-1])

Solution (Python):

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

INF=10**9

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

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


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


print(dp[N][H])

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

dp = [(j + M[0][0] - 1) // M[0][0] * M[0][1] for j in range(H + 1)]
for i in range(1, N):
    Ai, Bi = M[i]
    ndp = [0] * (H + 1)
    if Ai >= H:
        ndp[0:H + 1] = [min(dp[j], Bi) for j in range(H + 1)]
    else:
        ndp[0:Ai + 1] = [min(dp[j], Bi) for j in range(Ai + 1)]
        for j in range(Ai + 1, H + 1):
            ndp[j] = min(dp[j], ndp[j - Ai] + Bi)
    dp = ndp
print(dp[H])

Solution (Python):
import sys

def main():
    h_and_n_s = sys.stdin.readline().strip().split(' ')
    h, n = [int(s) for s in h_and_n_s]
    a = [-1] * n
    b = [-1] * n

    
    
    for i in range(n):
        a[i], b[i] = [int(s) for s in sys.stdin.readline().strip().split(' ')]
        
        
        

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

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

            dp[point] = min(dp[point], dp[point-a[i]] + b[i])

    print(dp[h])


if __name__ == '__main__':
    main()

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

dg = 10**5

ba = []
for _ in [0]*n:
    a,b = map(int,input().split())
    if a >= h:
        a = h
    ba.append(b*dg+a)
ba.sort()

d = [10**9]*(h+1)

d[0] = 0

for i in range(1,h+1):
    for e in ba:
        a,b = e%dg,e//dg
        if i<=a:
            if d[i] > b:
                d[i] = b
        else:
            if d[i] > d[i-a]+b:
                d[i] = d[i-a]+b

print(d[-1])

Solution (Python):
import bisect

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

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

dp = [float('inf')]*(H+1)
dp[0] = 0
for h in range(1, H+1):
  for a, b in AB:
    if h - a <= 0:
      cost = b
    else:
      cost = dp[h-a] + b
    dp[h] = min(dp[h], cost)

print(dp[H])

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

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

for h in range(1,H+1):
    dp[h][0] = 10**9

for n in range(1,N+1):
    for h in range(H+1):
        if h >= AB[n-1][0]:
            dp[h][n] = min(dp[h-AB[n-1][0]][n]+AB[n-1][1] , dp[h][n-1])
        else:
            dp[h][n] = dp[h][n-1]



        
ans = dp[H][N]
for n in range(N):
    for h in range(H):
        if (H-AB[n][0])<=h:
            ans = min(ans,dp[h][N]+AB[n][1])

print(ans)

Solution (Python):

H,n = map(int,input().split())
A = [0 for _ in range(n)]
B = [0 for _ in range(n)]
min_eff = 9999.
for i in range(n):
    A[i],B[i] = map(int,input().split())
    min_eff = min(min_eff,A[i]/B[i])

dp = [[int(H/min_eff+1) for _ in range(H+1)] for _ in range(n+1)]
for i in range(n+1):
    dp[i][0] = 0


for i in range(n):
    for h in range(H+1):
        idx = max(0,h-A[i])
        dp[i+1][h] = min(dp[i+1][idx] + B[i],dp[i][h])

print(int(dp[n][H]))

Solution (Python):
H, N = map(int, input().split())
INF = 10 ** 12

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


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





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

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










print(dp[N][H])

Solution (Python):
import sys
def input(): return sys.stdin.readline().rstrip()

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

    dp = [10**9+1] * (H+1)
    dp[0] = 0
    for a, b in AB:
        for i in range(1, H+1):
            if i - a >= 0:
                v = dp[i-a] + b
            else:
                v = b
            if dp[i] > v:
                dp[i] = v

    print(dp[H])

if __name__ == '__main__':
    main()

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

dp = [[10 ** 9] * (H + 1) for _ in range(N + 1)]
dp[0][0] = 0
X.sort(key=lambda x: -x[-1])

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

Solution (Python):
H, N = map(int, input().split())
dp = [0] * (H+1)
A, B = map(int, input().split())
for j in range(1, H+1):
    dp[j] = max(dp[max(j-A,0)] + B, dp[j])
for i in range(1,N):
    A, B = map(int, input().split())
    for j in range(1, H+1):
        dp[j] = min(dp[max(j-A,0)] + B, dp[j])
print(dp[H])

Solution (Python):
H,N = map(int,input().split())
X = []
for _ in range(N):
    a,b = map(int,input().split())
    X.append([a,b])
dp = [10000000000000 for i in range(H+1)] 
dp[0] = 0
for i in range(1,H+1):
    for j in range(N):
        a = X[j][0]
        b = X[j][1]
        dp[i] = min(dp[i],dp[max(0,i-a)] + b)

print(dp[H])

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

    dp = [999999999999999999999 for _ in range(H + 1)]
    dp[H] = 0

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

    print(dp[0])


main()

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

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

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

Solution (Python):
H,N=map(int,input().split())
A=[0]*N
B=[0]*N
for i in range(N):
    a,b=map(int,input().split())
    A[i]=a
    B[i]=b
    
inf=10**9
dp=[[inf] * (H+1) 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+1):
        if j-A[i]>=0:
            dp[i+1][j]=min(dp[i][j],dp[i+1][j-A[i]]+B[i])
        else:
            dp[i+1][j]=min(dp[i][j],dp[i][0]+B[i])

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

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

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

def l():
    a, b = map(int, input().split())
    return P(a, b)

class P:
    def __init__(self, f, s):
        self.f = f
        self.s = s

    def __lt__(self, other):
        return self.s * other.f < other.s * self.f

AB = [l() for _ in range(N)]
AB = sorted(AB)

HMAX = H + 10000

dp = [INF] * (HMAX + 1)
dp[0] = 0
for i in range(HMAX):
    for p in AB:
        if i + p.f > HMAX:
            continue
        dp[i + p.f] = min(dp[i + p.f], dp[i] + p.s)

for i in range(HMAX - 1, -1, -1):
    dp[i] = min(dp[i + 1], dp[i])

print(dp[H])

Solution (Python):

H, N = map(int, input().split(' '))

lim = float('inf')
powers = [lim for _ in range(H+1)]
powers[0] = 0

for _ in range(N):
    A, B = map(int, input().split(' '))
    for i in range(H):
        if powers[i] != lim:
            if i+A > H:
                powers[H] = min(powers[H], powers[i] + B)
            else:
                powers[i+A] = min(powers[i+A], powers[i] + B)



print(powers[H])

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

h,n=map(int,input().split())
inf=float("inf")

DP=[inf]*(h+1)
DP[0]=0
for i in range(n):
  a,b=map(int,input().split())
  for j in range(h+1):
    DP[min(h,j+a)]=min(DP[j]+b,DP[min(h,j+a)])
print(DP[h])

Solution (Python):
h,n = map(int, input().split())
ls = [list(map(int, input().split())) for i in range(n)]
INF = 1001001001001
dp = [[INF]*(h+1) for _ in range(n+1)]

for i in range(n+1):
    dp[i][0] = 0


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

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

Solution (Python):
import sys
h, n = map(int, input().split())
waza = []
effic = []
for _ in range(n):
    a, b = map(int, sys.stdin.readline().split())
    waza.append([a, b])
dp = [10**10] * (h+1)
dp[0] = 0
for i in range(n):
    for j in range(h):
        if dp[j] != 10**10:
            target = j + waza[i][0]
            if target > h:
                target = h
            if dp[target] > dp[j] + waza[i][1]:
                dp[target] = dp[j] + waza[i][1]
print(dp[h])

Solution (Python):
h, n = map(int, input().split())
ab = []
for i in range(n):
    ab.append(list(map(int, input().split())))
num = [float("inf")] * (h + 1)
num[0] = 0
for i in range(h):
    mp = []
    for j in range(n):
        if (i + 1) - ab[j][0] < 0:
            mp.append(ab[j][1])
        else:
            mp.append(num[i + 1 - ab[j][0]] + ab[j][1])
    num[i + 1] = min(mp)
print(num[h])

Solution (Python):
inf = 10 ** 9
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)

dp = [0] * (h + 1)

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

print(dp[h])

Solution (Python):
import sys
input = sys.stdin.readline
def solve():
  h,n = (int(i) for i in input().split())
  query = []
  for i in range(n):
    a,b = (int(i) for i in input().split())
    query.append((a,b))
  ap = [10**9+7]*(h+10003)
  ap[0] = 0
  for i in range(h+1):
    nowap = ap[i]
    for a,b in query:
      if i+a <= h+10001:
        ap[i+a] = min(ap[i+a],nowap+b)
      else:
        continue
  ans = 10**9+7
  for i in range(h,h+10001):
    ans = min(ans,ap[i])
  print(ans)

solve()

Solution (Python):
def main():
    H, N = (int(i) for i in input().split())
    AB = [[int(i) for i in input().split()] for j in range(N)]
    dp = [[(10**8) for i in range(H + 1)] for j in range(N+1)]
    for i in range(N+1):
        dp[i][0] = 0

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


if __name__ == '__main__':
    main()

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

inf = 10 ** 10
DP = [[inf] * (H + 1) for _ in range(N)]

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

print(DP[-1][H])

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

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

Solution (Python):
ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))

h,n = mi()
a = []
for i in range(n):
    aa,bb = mi()
    a.append([aa,bb])
inf =  10 **9   
dp = [inf] * (h+1)
dp[0] = 0
for i in range(n):
    for j in range(h):
        if j + a[i][0] <= h:
            dp[j + a[i][0]] = min(dp[j+a[i][0]],dp[j] + a[i][1])
        else:
            dp[h] = min(dp[h],dp[j] + a[i][1])
print(dp[h])

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

dps = [0 for i in range(h + 1)]
for i in range(1, h + 1):
  ans = 10 ** 10
  for m in monster:
    ans = min(ans, dps[max(i - m[0], 0)] + m[1])
  dps[i] = ans

print(dps[h])

Solution (Python):
INF = 10**12
maxH = 2 * 10**4 + 10

def solve():
    H, N = map(int, input().split())
    ABs = [tuple(map(int, input().split())) for _ in range(N)]

    dp = [INF] * (maxH+1)
    dp[0] = 0
    for A, B in ABs:
        for h in range(maxH-A+1):
            h2 = h + A
            dp2 = dp[h] + B
            if dp2 < dp[h2]:
                dp[h2] = dp2

    print(min(dp[H:]))


solve()

Solution (Python):
def two_int():
    N, K = map(int, input().split())
    return N,K

def one_int():
    return int(input())

def one_str():
    return input()

def many_int():
    return list(map(int, input().split()))



H,N = two_int()

dp = [0 for j in range(H)]

magics = []
for i in range(N):
    A,B = two_int()
    magics.append([A,B])

for i in range(H):
    temps=[]
    for [A,B] in magics:
        ind = i-A
        if ind >= 0:
            temps.append(dp[ind] + B)
        else:
            temps.append(B)



    dp[i] = min(temps)

print(dp[-1])

Solution (Python):
import sys
import numpy as np

inf = float('inf')

h, n, *ab = map(int, sys.stdin.read().split())
a, b = np.array(ab, dtype=np.int64).reshape(n, 2).T

def main():
    dp = np.zeros(h+1, dtype=np.int64)
    for i in range(1, h+1):
        dp[i] = np.amin(dp[np.maximum(i-a, 0)] + b)
        
    return dp[h]

if __name__ == '__main__':
    ans = main()
    print(ans)

Solution (Python):
H,N=map(int,input().split())
ab = [tuple(map(int,input().split())) for _ in range(N)]
a = [elem[0] for elem in ab]
h = max(a)
dp = [[10**9]*(H+1+h) for _ in range(N+1)]
dp[0][0]=0
for i in range(N):
    for j in range(H+1+h):
        bb = ab[i][0]
        if j < bb:
            dp[i+1][j] = dp[i][j]
        else:
            dp[i+1][j] = min(dp[i][j], dp[i+1][j-bb] + ab[i][1])
print(min(dp[N][H:]))

Solution (Python):
INF = 10**18

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

dp = [INF]*(2*(10**4)+1)
dp[0] = 0

for i in range(N):
    d = magic[i][0]
    mp = magic[i][1]
    for j in range(d,2*(10**4)+1):
        dp[j] = min(dp[j-d]+mp,dp[j])
ans = INF
for i in range(H,2*(10**4)+1):
    ans = min(ans,dp[i])

print(ans)

Solution (Python):
H, N = map(int, input().split())
magiclist = [0]*N
dp = [0] * (N+1)
for s in range(N+1):
    dp[s] = [10**9] * (H + 1)
    dp[s][0] = 0
for i in range(N):
    magiclist[i] = [0]*2
    damage, mp = map(int, input().split())
    magiclist[i][0], magiclist[i][1] = damage, mp
    for j in range(H + 1):
        if j - damage < 0:
            dp[i + 1][j] = dp[i][j]
        else:
            dp[i + 1][j] = min(dp[i][j], (mp + dp[i + 1][j - damage]))
kouho = dp[N][H]
for h in range(N):
    kouho = min(kouho, min(dp[N][H-magiclist[h][0]:H])+magiclist[h][1])
print(kouho)

Solution (Python):
from math import ceil
h,n = map(int,input().split())

inf = float('INF')
dp = [inf for i in range(h+1)]
dp[0] = 0
for _ in range(n):
    a,b = map(int,input().split())
    for i in range(h+1):
        idx = i-a if i >= a else 0
        if i >= a and dp[i] > dp[idx] + b:
            dp[i] = dp[i-a] + b
        elif i <= a and b < dp[i]:
            dp[i] = b
print(dp[h])

Solution (Python):
h,n=map(int,input().split())
AB=[]
for _ in range(n):
    AB.append(list(map(int,input().split())))
dp=[0]+[float("INF")]*h
for i in range(1,h+1):
    for a,b in AB:
        if i<=a:
            dp[i]=min(dp[i],b)
        else:
            dp[i]=min(dp[i],b+dp[i-a])
print(dp[-1])

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


for i in range(n):
    a,b = map(int,input().split())
    for j in range(h+1):
        if dp[i+1][j] > dp[i][j]:
            dp[i+1][j] = dp[i][j]
        nex = min(h,j+a)
        if dp[i+1][nex] > dp[i+1][j] + b:
            dp[i + 1][nex] = dp[i + 1][j] + b





print(dp[-1][h])

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


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

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

for h in range(1, H + 1):
    for n in range(N):
        a, b = mahous[n]
        tairyoku = max(0, h - a)
        
        dp[h] = min(dp[h], dp[tairyoku] + b)
    

print(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)]

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

answer = INF
for a, b in AB:
  for i in range(H + 1):
    if dp[i] != INF:
      if i + a < H:
        dp[i + a] = min(dp[i + a], dp[i] + b)
      else:
        answer = min(dp[i] + b, answer)
        
print(answer)

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

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

def chmin(l, i, v):
  if l[i] > v:
    l[i] = v
    return True
  return False

def chmax(l, i, v):
  if l[i] < v:
    l[i] = v
    return True
  return False


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

for h in range(1, H+1):
  
  
  
  for A, B in AB:
    chmin(dp, h, B if h <= A else dp[h - A] + B)


print(dp[H])

Solution (Python):
h,n = map(int,input().split())
now = [10**10 for _ in range(h+1)]
now[0] = 0
for _ in range(n):
  a,b = map(int,input().split())
  for i in range(1,h+1):
    if i - a < 0:
      now[i] = min(now[i],b)
    else:
      now[i] = min(now[i],now[i-a]+b)
print(now[-1])

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

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

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

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

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

Solution (Python):
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 = [float('inf')] * (H + max(A) + 5)
    dp[0] = 0
    for i in range(N):
        for j in range(H):
            dp[j + A[i]] = min(dp[j] + B[i], dp[j + A[i]])

    ans = float('inf')
    for i in range(H, H + max(A) + 1):
        ans = min(ans, dp[i])

    print(ans)


    
    


if __name__ == "__main__":
    main()

Solution (Python):
h,n=map(int,input().split())
l=[list(map(int,input().split())) for i in range(n)]
m=[]
for i in range(n):
  m.append(l[i][1])
x=min(m)
dp=[999999999999 for i in range(10**4+1)]
dp[0]=0
for i in range(10**4+1):
  for j in range(n):
    if i>=l[j][0]:
      dp[i]=min(dp[i-l[j][0]]+l[j][1],dp[i])
  dp[i]=min(dp[i-1]+x,dp[i])
ans=[]
for i in range(h,10**4+1):
  ans.append(dp[i])
print(min(ans))

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

    dp = [float("inf")]*(H + 10010)
    mx = 10**8
    for a,b in AB:
        dp[min(a,H)] = min(dp[min(a,H)],b)
    for i in range(1,H + 1):
        if dp[i] > mx:
            continue
        for a,b in AB:
            if i + a > H:
                dp[H] = min(dp[H],dp[i] + b)
            else:
                dp[i + a] = min(dp[i + a],dp[i] + b)
    print(dp[H])


if __name__ == "__main__":
    main()

Solution (Python):

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

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

for i in range(N):

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

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

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

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

ans = dp[n][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 = [100000000000000 for i in range(h+1)]
dp[0] = 0

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

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

M = []

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

DP = [[10**9]*(N+1) for i in range(H+1)]

DP[H][0] = 0

for i in range(N):
    m = 10**9
    for j in range(H+1):
        h = H-j
        DP[h][i+1] = DP[h][i]
        if h+M[i][0] <= H and h!=0:
            DP[h][i+1] = min(DP[h][i], DP[h+M[i][0]][i+1]+M[i][1])
        elif h==0:
            DP[h][i+1] = min(DP[h][i],m + M[i][1])
        if h<=M[i][0]:
            m = min(m,DP[h][i+1])
            

print(DP[0][N])

Solution (Python):
"""
NTC here
"""
import sys
inp= sys.stdin.readline
input = lambda : inp().strip()
flush= sys.stdout.flush




def iin(): return int(input())
def lin(): return list(map(int, input().split()))





def main():
    h, n = lin()
    a = [lin() for i in range(n)]
    ans = [-1]*(h+1)
    ans[0] = 0
    for i in range(1, h+1):
        ans[i] = min([
            ans[max(0, i-j)]+k for j, k in a
            ])
        
        
    print(ans[h])



            
        

        
main()

Solution (Python):

from __future__ import division, print_function

import os
import sys
from io import BytesIO, IOBase

if sys.version_info[0] < 3:
    from __builtin__ import xrange as range
    from future_builtins import ascii, filter, hex, map, oct, zip


def main():
    h, n = map(int, input().split())
    m = [tuple(map(int, input().split())) for _ in range(n)]

    a, b = m[0]
    dp = [[10**18] * (h + 1) for _ in range(n)]
    dp[0] = [((i + a - 1) // a) * b for i in range(h + 1)]
    for i in range(1, n):
        a, b = m[i]
        for j in range(h + 1):
            dp[i][j] = min(dp[i - 1][j], b + dp[i][max(0, j - a)])

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




BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


def print(*args, **kwargs):
    """Prints the values to a stream, or to sys.stdout by default."""
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()


if sys.version_info[0] < 3:
    sys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)
else:
    sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)

input = lambda: sys.stdin.readline().rstrip("\r\n")



if __name__ == "__main__":
    main()

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

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

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

    dp[H] = 0

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

    print(dp[0])

if __name__ == "__main__":
    main()