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

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

amax = max(a for a,b in ls)

dp = [0]*(h+amax)

for i in range(1,h+amax):
  p = max(1,2)
  dp[i] = min(dp[i-a]+b for a,b in ls)

print(min(dp[h:]))

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

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

amax = max(a for a,b in ls)

dp = [0]*(h+amax)

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

print(min(dp[h:]))

Solution (Python):
h, n = map(int, input().split())
ab = [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(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(0, j-a)] + b)

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

Solution (Python):
from functools import lru_cache
import sys

H,N = [int(i) for i in input().rstrip().split(' ')]
M = [[int(i) for i in input().rstrip().split(' ')] for _ in range(N)]

sys.setrecursionlimit(10**9)
DP = [0]*(H+1)

for x in range(1,H+1):
    DP[x] = min(DP[max(x-a,0)] + b for a,b in M)

print(DP[H])

Solution (Python):
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)

print(min(dp[H:]))

Solution (Python):
import numpy as np

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

a, b = ab[:, 0], ab[:, 1]
dp = np.zeros(h+1, dtype=np.int)
for i in range(1, h+1):
    dp[i] = np.min(dp[np.maximum(i-a, 0)] + b)

print(dp[h])

Solution (Python):

MOD = 10 ** 9 + 7
INFI = 10**10

import math
 
import itertools
 

 
import copy
from functools import lru_cache
 
def sosuhante(n):
    for k in range(2, int(math.sqrt(n))+1):
        if n% k ==0:
            return False
    return True
def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n
 
    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]
 
    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot
 
    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])
 
    return result
 
def kingaku(a,b,n):
    keta=len(str(n))
    return a*n+b*keta
 
def my_index(l, x, default=False):
    if x in l:
        return l.index(x)
    else:
        return default
 


 
 
 
def main():
    h,n=map(int,input().split()) 
    ab=[list(map(int,input().split())) for i in range(n)]
    maxa = max(a for a, b in ab)
    dp=[INFI for i in range(h+maxa)]
    dp[0]=0
 
 
    def f(h):
 
        for a,b in ab:
            for j in range(h+maxa):
                dp[j]=min(dp[j],dp[j-a]+b)
        return min(dp[h:])
 
    print(f(h))
 
 
if __name__ == "__main__":
    main()

Solution (Python):

MOD = 10 ** 9 + 7
INFI = 10**10

import math
 
import itertools
 

 
import copy
 
 
def sosuhante(n):
    for k in range(2, int(math.sqrt(n))+1):
        if n% k ==0:
            return False
    return True
def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n
 
    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]
 
    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot
 
    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])
 
    return result
 
def kingaku(a,b,n):
    keta=len(str(n))
    return a*n+b*keta
 
def my_index(l, x, default=False):
    if x in l:
        return l.index(x)
    else:
        return default
 


 
 
 
def main():
    h,n=map(int,input().split()) 
    a=[]
    b=[]
    for i in range(n):
        x,y=map(int,input().split())
        a.append(x)
        b.append(y)
 
    dp=[INFI for i in range(h+1)]
    dp[0]=0
    for i in range(n):
        for j in range(len(dp)):
            if j-a[i]<0:
                dp[j] = min(dp[j], dp[0] + b[i])
            else:
                dp[j]=min(dp[j],dp[j-a[i]]+b[i])
 
    print(dp[h])
 
 
if __name__ == "__main__":
    main()

Solution (Python):
def main():
  h, n = map(int, input().split())
  l = [list(map(int, input().split())) for i in range(n)]

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

  for i in range(h):
    if dp[i] == 10 ** 8 + 1:
        continue
    for a, b in l:
      x = dp[i] + b
      if dp[i + a] > x:
        dp[i + a] = x

  print(min(dp[h:]))

main()

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

    dp = [100000000] * (H + 10 ** 4 + 1)
    dp[0] = 0
    for i in range(H):
        if dp[i] == 100000000:
            continue
        for a, b in AB:
            t = dp[i] + b
            if t < dp[i + a]:
                dp[i + a] = t
    print(min(dp[H:]))


main()

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

dp = [0] * (H + 1)
for h in range(1, H + 1):
    dp[h] = min([dp[max(h - a, 0)] + b for a, b in AB])

print(dp[-1])

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

dp = [0] * (H + 1)
for h in range(1, H + 1):
    dp[h] = min([dp[max(h - a, 0)] + b for a, b in AB])

print(dp[-1])

Solution (Python):

import numpy
import sys
from functools import lru_cache
sys.setrecursionlimit(10**6)

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

AB.sort(key=lambda ab: (ab[1] / ab[0], ab[0]))

@lru_cache(maxsize=None)
def dp(h):
    if h <= 0:
        return 0
    else:
        best = float('inf')
        for a, b in AB:
            mp = b + dp(h -a)
            if mp < best:
                best = mp
            else:
                break
        return best

print(dp(h))

Solution (Python):

H, N = map(int, input().split())
L = []
for i in range(N):
    L.append(list(map(int, input().split())))
dp = [float("inf") for _ in range(H+1)] 
dp[0] = 0
top = 10**9
for i in range(1, H+1):
    for j in range(N):
        a, b = L[j]
        if i <= a:
            dp[i] = min(dp[i], b)
        else:
            dp[i] = min(dp[i], dp[i-a] + b)
    
print(dp[H])

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

Solution (Python):
from sys import stdin
H, N = [int(_) for _ in stdin.readline().rstrip().split()]
A = []
B = []

def chmin(a, b):
    if a > b:
        return b
    return a

for i in range(N):
    a, b = [int(_) for _ in stdin.readline().rstrip().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)] = chmin(dp[min(j+A[i], H)], dp[j]+B[i])
print(dp[H])

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


dp = [10**9]*(H+1)

dp[0] = 0



for i in range(N):
    a, b = ab[i]
    for j in range(H):
        
        k = min(j + a, H)
        
        dp[k] = min(dp[k], dp[j] + b)

print(dp[H])

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
mod2 = 998244353
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


def main():
    h,n = LI()
    ab = [LI() for _ in range(n)]
    r = [inf] * (h+10**4+2)
    r[0] = 0
    for a,b in ab:
        for i in range(h):
            t = r[i] + b
            if r[a+i] > t:
                r[a+i] = t

    return min(r[h:])


print(main())

Solution (Python):
import numpy as np

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

a, b = ab[:, 0], ab[:, 1]
dp = np.zeros(h+1, dtype=np.int)
for i in range(1, h+1):
    dp[i] = np.min(dp[np.maximum(i-a, 0)] + b)

print(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())
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):
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+1)
    dp[0] = 0
    for i in range(N):
        for j in range(H+1):
            dp[j] = min(dp[j], dp[max(j-A[i], 0)] + B[i])
    print(dp[H])


if __name__ == "__main__":
    main()

Solution (Python):


H,N=map(int,input().split())
L=[[0,0]]
for i in range(N):
    a,b=map(int,input().split())
    L.append([a,b])
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][max(j-L[i][0],0)] + L[i][1])
print(dp[N][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=[[0]*(H+1) for i in range(N)]
DP.insert(0,[float("inf")]*(H+max(A)))
DP[0][0]=0

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

print(DP[N][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=[[0]*(H+max(A)) for i in range(N)]
DP.insert(0,[10**8+1]*(H+max(A)))
DP[0][0]=0

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

print(DP[N][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=[[0]*(H+max(A)) for i in range(N)]
DP.insert(0,[10**8+1]*(H+max(A)))
DP[0][0]=0

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

print(DP[N][H])

Solution (Python):
import sys
import socket

if socket.gethostname() in ['N551J', 'F551C']:
    sys.stdin = open('e1.in')


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


def read_int():
    return int(input())


def read_str_list():
    return input().split()


def read_str():
    return input()

inf = 10 ** 20

def solve():
    H, n = read_int_list()
    a, b = [0] * n, [0] * n
    for i in range(n):
        a[i], b[i] = read_int_list()
    cost = [0] * (H+1)
    for h in range(1, H+1):
        c = inf
        for i in range(n):
            health = h - a[i]
            if health < 0:
                health = 0
            if c > cost[health] + b[i]:
                c = cost[health] + b[i]
        cost[h] = c

    
    

    return cost[H]



def main():
    res = solve()
    print(res)


if __name__ == '__main__':
    main()

Solution (Python):
HP,n = map(int,input().split())
s = [tuple(map(int,input().split())) for i in range(n)]


dp = [float('inf')]*(HP+1) 
dp[0] = 0
for damage, cost in s:
    for hp in range(HP):
        next_idx = min(hp+damage, HP)
        dp[next_idx] = min(dp[next_idx], dp[hp]+cost)
print(dp[-1])

Solution (Python):
def wczytaj_liste():
    ciag = input()
    rozdzielona_lista = ciag.split()
    odp = []
    for wyraz in rozdzielona_lista:
        liczba = int(wyraz)
        odp.append(liczba)
    return odp

def rzucanie_zaklenc(zycie, lista_zaklenc):
    koszt_zaklenc = [10**9] * (zycie+1)
    koszt_zaklenc[0] = 0
    for damage, cost in lista_zaklenc:
        for i in range(zycie+1):
            if i - damage >= 0:
                if cost+koszt_zaklenc[i-damage]< koszt_zaklenc[i]:
                    koszt_zaklenc[i] = cost+koszt_zaklenc[i-damage]
            else:
                if cost < koszt_zaklenc[i]:
                    koszt_zaklenc[i] = cost
    return koszt_zaklenc[zycie]

def E():
    H, N = wczytaj_liste()
    zaklencia = []
    for i in range(N):
        damage, cost = wczytaj_liste()
        zaklencia.append((damage, cost))
    print(rzucanie_zaklenc(H, zaklencia))

E()

Solution (Python):
import sys

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

dp = [float('inf') for _ in range(H + max(AB)[0] + 1)]
dp[0] = 0
for h in range(H + max(AB)[0] + 1):
    for n in range(N):
        if h - AB[n][0] >= 0:
            dp[h] = min(dp[h - AB[n][0]] + AB[n][1], dp[h])

print(min(dp[H:]))

Solution (Python):
h,n = map(int,input().split())
L = []
for i in range(n):
  l = list(map(int,input().split()))
  L.append(l)
dp = [10**8]*10001
dp[0] = 0
for i in range(n):
  dp[L[i][0]] = L[i][1]
for i in range(10001):
  for j in range(n):
    if i-L[j][0] >= 0:
      dp[i] = min(dp[i],dp[i-L[j][0]]+L[j][1])
for i in range(9999,-1,-1):
  if dp[i] > dp[i+1]:
    dp[i] = dp[i+1]
print(dp[h])

Solution (Python):
import math

def main():
    H,N=map(int,input().split())

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

    for i in range(N):
        A,B=map(int,input().split())
        if A>=H:
            
            if B < dp[-1]:
                dp[-1]=B
        else:
            for j in range(A,H+1):
                
                if dp[j-A]+B<dp[j]:
                    dp[j]=dp[j-A]+B

                if j > H-A:
                    
                    if dp[j]+B < dp[-1]:
                        dp[-1]=dp[j]+B

    print(dp[-1])

main()

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

Solution (Python):
import numpy as np

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

A = np.zeros(N, dtype = int)
B = np.zeros(N, dtype = int)

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

dp[0] = 0
for i in range(1,H+1):
    dp[i] = np.amin( dp[np.maximum(i-A,0)] + B )

print(int(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())
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
H, N = map(int, sys.stdin.readline().split())
m = map(int, sys.stdin.read().split())
AB = zip(m, m)
INF = 10**20
dp = [INF]*(H+10**4)
dp[0] = 0
for a, b in AB:
    for j in range(H+10**4):
        dp[j] = min(dp[j], dp[j-a] + b if j-a >= 0 else INF)
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 = [0] + [-1] * h
INF = 10**18
for hp in range(1, h+1):
    ret = INF
    for i in range(n):
        if hp - a[i] >= 0:
            ret = min(ret, dp[hp-a[i]] + b[i])
        else:
            ret = min(ret, b[i])
    dp[hp] = ret
print(dp[h])

Solution (Python):
import sys


def resolve():
    H, N = map(int, sys.stdin.readline().split())
    m = map(int, sys.stdin.read().split())
    AB = zip(m, m)
    INF = 10**20
    dp = [INF]*(H+10**4)
    dp[0] = 0
    for a, b in AB:
        for j in range(H+10**4):
            dp[j] = min(dp[j], dp[j-a] + b if j-a >= 0 else INF)
    return min(dp[H:])


if __name__ == '__main__':
    print(resolve())

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 math
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 = []
for i in range(h + max(a)):
    dp.append(pow(2, 31) - 1)
dp[0] = 0

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

print(min(dp[h:]))

Solution (Python):

def solve(N, W, ws, vs):
    dp = [float("inf")] * (W + 1)
    dp[0] = 0
    for i in range(N):
        
        v = vs[i]
        w = ws[i]
        for j in range(w, W + 1):
            dp[j] = min(dp[j - w] + v, dp[j])
    return dp


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

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


dp = solve(n, h+10**4+1, ws, vs)

print(min(dp[h:]))

Solution (Python):
import sys

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

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

for a,b in AB:
    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):
H, N = map(int, input().split())
AB = list(list(map(int, input().split())) for _ in range(N))

def main2(H, N, AB):
    inf = 2**31 -1
    dp = [inf] * (H + max(a for a, _ in AB))
    dp[0] = 0
    for i in range(1, len(dp)):
        dp[i] = min(dp[i-a]+b for a,b in AB)
    print(min(dp[H:]))

main2(H,N,AB)

Solution (Python):
import sys
input = sys.stdin.readline
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") for j in range(H+1)] for i in range(N+1)]
for i in range(N):
    for j in range(H+1):
        if j <= A[i]:
            dp[i+1][j] = min(dp[i][j], B[i])
        else:
            dp[i+1][j] = min(dp[i][j], dp[i+1][j-A[i]] + B[i])
print(dp[N][H])

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

INF=10**10
dp=[INF]*(10**5+5)
dp[0]=0
for i in range(h+max(A)+2):
  m=dp[i]
  for j in range(n):
    if i-A[j]<0:
      continue
    a=dp[i-A[j]]+B[j]
    if a<m:
      m=a
  dp[i]=m
  for j in range(i+1,i+1-max(A)-3,-1):
    if dp[j]>dp[j+1]:
      dp[j]=dp[j+1]
print(dp[h])

Solution (Python):
h,n=map(int,input().split())
a = [0]*n
b = [0]*n
for i in range(n):
    a[i],b[i] = map(int,input().split())
dp = [1e9]*(h+1)
dp[h]=0
for i in range(h+1):
    now=h-i
    if dp[now]==1e9:
        continue
    for j in range(n):
        now2=max(now-a[j],0)
        dp[now2]=min(dp[now2],(dp[now]+b[j]))
print(dp[0])

Solution (Python):
h,n=map(int,input().split())
a = [0]*n
b = [0]*n
for i in range(n):
    a[i],b[i] = map(int,input().split())
dp = [0]*(h+1)
for i in range(h+1):
    dp[i]=1000000000
dp[h]=0
for i in range(h+1):
    now=h-i
    if dp[now]==1e9:
        continue
    for j in range(n):
        now2=max(now-a[j],0)
        dp[now2]=min(dp[now2],(dp[now]+b[j]))
print(dp[0])

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

Solution (Python):
H, N = (int(i) for i in input().split())
A = [0]*N
B = [0]*N
for i in range(N):
    A[i], B[i] = (int(j) for j in input().split())
A_max = max(A)

DP = [0]*(H+A_max)
for i in range(1, H+A_max):
    dp = float('inf')
    for a, b in zip(A,B):
        if i-a>=0:
            dp = min(dp, DP[i-a] + b)
    DP[i] = dp
print(min(DP[H:]))

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

max_attack=max(at[0] for at in attack)

dp = [0]*(h+max_attack)
for i in range(1,h+max_attack):
    at=[]
    for a,b in attack:
        at.append(dp[i-a]+b)
    dp[i]=min(at)
print(min(dp[h:]))

Solution (Python):
def solve(h, n, AB):
    size = h + max(a for a, _ in AB) 
    dp = [-1] * size
    dp[0] = 0
    for i in range(1, size):
        
        dp[i] = min(b if a >= i else dp[i - a] + b for a, b in AB)
    return min(dp[h:])

_h, _n = map(int, input().split())
_AB = [list(map(int, input().split())) for _ in range(_n)]
print(solve(_h, _n, _AB))

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

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

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

print(dp[-1])

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)

G = [0]*(H+1)

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

Solution (Python):
import numpy as np

h, n = map(int, raw_input().split())
a = np.zeros(n, dtype=int)
b = np.zeros(n, dtype=int)
for i in range(n):
    a[i], b[i] = map(int, raw_input().split())
dp = np.zeros(10001, dtype=int)
for i in range(1, 10001):
    dp[i] = (dp[i - a] + b).min()
print(dp[h])

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

DP = [10**9]*(H+1)
DP[0] = 0
for a,b in magic:
    for i in range(min(a,H+1)):
        DP[i] = min(DP[i],b)
    for i in range(a,H+1):
        DP[i] = min(DP[i],DP[i-a]+b)
print(DP[-1])

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

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

for i in range(1, len(dp)):
    for x, y in ab:
        if i - x > 0:
            dp[i] = min(dp[i], dp[i - x] + y)
        else:
            dp[i] = min(dp[i], y)

print(dp[h])

Solution (Python):
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] = list(map(int, input().split()))

max_damage = max(A)
dp = [0 for _ in range(H + max_damage)]
for i in range(1, H + max_damage):
    dp[i] = min(dp[i - a] + b for a, b in zip(A, B))

print(min(dp[H:]))

Solution (Python):
INF = 10000000000
a=[0 for i in range(int(1e5))]
b=[0 for i in range(int(1e5))]
ans = [INF for i in range(int(1e5))]

def main():
    h,n = map(int,input().split())
    for i in range(n):
        tmp = list(map(int,input().split()))
        a[i] = tmp[0]
        b[i] = tmp[1]
        index = min(h,a[i])
        if b[i] < ans[index]:
            ans[index] = b[i]
    
    
    for i in range(h):
        if ans[i]!=INF:
            for j in range(n):
                index = min(h,a[j]+i)
                if ans[i]+b[j] < ans[index]:
                    ans[index] = ans[i]+b[j]
    print(ans[h])
if __name__=="__main__":
    main()

Solution (Python):




get = lambda: int(raw_input().strip())
getl = lambda: raw_input().strip()
gets = lambda: list(map(int, raw_input().strip().split()))
getss = lambda n: [gets() for _ in range(n)]

h, N = gets()
AB = getss(N)

dp = [0] + [float('inf')] * h
for a, b in AB:
    for i in range(h):
        j = min(i + a, h)
        dp[j] = min(dp[j], dp[i] + b)
print(dp[h])

Solution (Python):
import sys
import numpy as np

h, n = map(int, raw_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):



get = lambda: int(raw_input().strip())
getl = lambda: raw_input().strip()
gets = lambda: list(map(int, raw_input().strip().split()))
getss = lambda n: [gets() for _ in range(n)]

h, N = gets()
AB = getss(N)

dp = [0] + [float('inf')] * h
for a, b in AB:
    for i in range(h):
        j = min(i + a, h)
        dp[j] = min(dp[j], dp[i] + b)
print(dp[h])

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

a = [0]*N
b = [0]*N

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

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

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

Solution (Python):
h, n = map(int, input().split())
dp = [float('inf')]*(2*(10**4)+1)
dp[0] = 0
l = [list(map(int, input().split())) for _ in range(n)]

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

Solution (Python):

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

dp = [[10**10]*(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+magic[i][0], H)] = min(dp[i+1][min(j+magic[i][0], H)], dp[i+1][j] + magic[i][1])
print(dp[N][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 = [[10**10]*(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(H, j+A[i])] = min(dp[i][j]+B[i], dp[i+1][j]+B[i], dp[i+1][min(j+A[i], H)])

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

print(dp[N][H])

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

Solution (Python):
INF = float("inf")

H, N, *AB = map(int, open(0).read().split())

dp = [0] + [INF] * H

for a, b in zip(*[iter(AB)] * 2):
    for i in range(H + 1):
        idx = min(i + a, H)
        dp[idx] = min(dp[idx], dp[i] + b)

print(dp[H])

Solution (Python):
H, N, *AB = map(int, open(0).read().split())

dp = [0] * (H + max(AB[::2]))

for i in range(1, len(dp)):
    dp[i] = min(dp[i - a] + b for a, b in zip(*[iter(AB)] * 2))

print(min(dp[H:]))

Solution (Python):
INF = float("inf")

H, N, *AB = map(int, open(0).read().split())

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

for a, b in zip(*[iter(AB)] * 2):
    for i in range(a, len(dp)):
        if dp[i - a] != INF:
            dp[i] = min(dp[i], dp[i - a] + b)

print(min(dp[H:]))

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

DP = [0 for i in range(10**4+1)] 


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

print(DP[H])