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 = [int(i) for i in input().split()]
a, b = [0]*n, [0]*n

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

max_a = max(a)

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

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

    if i >= h:
        ans = min(ans, dp[i])
print(ans)

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 7)

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

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

INF = 10 ** 10
dp = [INF] * 20000
dp[0] = 0

for i in range(N):
    for h in range(H):
        a, b = MAGIC[i]

        if dp[h+a] > (dp[h] + b):
            dp[h+a] = dp[h] + b

print(min(dp[H:]))

Solution (Python):
def main():
    H,N = map(int, input().split())
    A = [None]*N
    B = [None]*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):
            if j + A[i] <= H:
                dp[j+A[i]] = min(dp[j+A[i]], dp[j]+B[i])
            else:
                dp[H] = min(dp[H], dp[j]+B[i])

    print(dp[H])


if __name__ == "__main__":
    main()

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

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


dp[0][0] = 0

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

print(dp[n][h])

Solution (Python):
def calc_m_value(M, A, B, N, h):
    return min([M[h - A[i]]+B[i] if A[i] <= h else B[i] for i in range(N)])
 
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)
 
M = [0] * (H+1)
for i in range(1, H+1):
    M[i] = calc_m_value(M, A, B, N, i)
 
print(M[H])

Solution (Python):
INF = 1145141919810893

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




dp = [INF]*20000
dp[0]=0



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





Ans=INF
for d in dp[H:]:
    Ans=min(Ans,d)
print(Ans)

Solution (Python):
import bisect
H,N = [int(x) for x in input().split()]
AB = [[int(x) for x in input().split()] for _ in range(N)]
dp = [[10**18]*(H+1) for _ in range(N+1)]
dp[0][0]=0
mi=10**9
for i in range(N):
  for w in range(H+1):
    dp[i+1][w]=min(dp[i+1][w],dp[i][w])
    dp[i+1][min(w+AB[i][0],H)]=min(dp[i+1][min(w+AB[i][0],H)],dp[i+1][w]+AB[i][1])
print(dp[N][H])

Solution (Python):
def main():
    import sys
    readline = sys.stdin.readline

    INF = 10 ** 8

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

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

    for _ in range(N):
        A, B = map(int, readline().split())
        for h in range(H):
            dp[min(H, h + A)] = min(dp[min(H, h + A)], dp[h] + B)

    print(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, b = map(int, input().split())
    A[i] = a
    B[i] = b



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

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

print(dp[N][H])

Solution (Python):
import math

def resolve():
    import sys
    input = sys.stdin.readline
    
    H, N = map(int, input().split())
    v = []
    w = []
    for i in range(N):
        a, b = map(int, input().split())
        v.append(a)
        w.append(b)

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

    
    for i in range(H):
        dp[0][i] = w[0] * (math.ceil((i + 1) / v[0])) 

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

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


if __name__ == "__main__":
    resolve()

Solution (Python):
INF = 10**12

H, N = map(int, input().split())
magics = [tuple(map(int, input().split())) for _ in range(N)]
dp = [[INF]*(H+1) for _ in range(N+1)]
dp[0][0] = 0
for i, (a, b) in enumerate(magics):
    for j in range(H+1):
        dp[i+1][j] = min(dp[i+1][j], dp[i][j])
        dp[i+1][min(H, j+a)] = min(dp[i+1][min(H, j+a)], dp[i+1][j] + b)
print(dp[N][H])

Solution (Python):
h,n=map(int,input().split())
l={}
ans=0
for i in range(n):
    a,b=map(int,input().split())
    if a in l:
        l[a]=min(l[a],b)
    else:
        l[a]=b
d=[0]*10005
for i in range(h):
    for j in l:
        a,b=j,l[j]
        x=d[i]+b
        y=min(10004,i+a)
        if i==0 or (d[i]!=0 and d[y]==0):
            if d[y]==0:
                d[y]=x
            else:
                d[y]=min(d[y],x)
        elif d[i]!=0 and d[y]!=0:
            d[y]=min(d[y],x)

for i in range(h,10005):
    if ans==0:
        ans=d[i]
    elif d[i]!=0:
        ans=min(ans,d[i])
print(ans)

Solution (Python):
def resolve():
    h, n = map(int, input().split())
    lab = []
    while True:
        try:
            a, b = map(int, input().split())
            lab.append([a, b])
        except:
            break
    cost = [0] * (h+1)
    for i in range(1, h+1):
        mb = 10 ** 8
        for j in range(n):
            if i < lab[j][0]:
                mb = min(mb, lab[j][1])
            else:
                mb = min(mb, cost[i - lab[j][0]] + lab[j][1])
        cost[i] = mb
    print(cost[h])
resolve()

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

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


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

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

    print(dp[N][H])


if __name__ == '__main__':
    main()

Solution (Python):
def run():
  H, N = map(int, input().split())
  ab_li = [tuple(map(int, input().split())) for n in range(N)]
  dp = [0]*(H+1)
  for i in range(1, H+1):
    new_li = []
    for n in range(N):
      a, b = ab_li[n]
      if a <= i:
        new_li.append(dp[i-a]+b)
      else:
        new_li.append(b)
    dp[i] = min(new_li)
  print(dp[-1])
  
if __name__ == '__main__':
  run()

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

skills=[]
for _ in range(n):
    x,y=map(int,input().split())
    skills.append((x,y))

INF=float("inf")

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

for a,b in skills:
    for hh in range(h,0,-1):
        if hh-a>=0:
            dp[hh-a]=min(dp[hh-a],dp[hh]+b)
        else:
            dp[0]=min(dp[0],dp[hh]+b)          
            
print(dp[0])

Solution (Python):
import numpy as np
import sys
read=sys.stdin.read

h,n,*ab=map(int,read().split())
a=np.array(ab[::2])
b=np.array(ab[1::2])

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

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

def dp(H,N,ls):
    table=[[float('inf')]*(H+1)] + [[0]*(H+1) for i in range(N)]
    for i in range(1,N+1):
        atk,cost=ls[i-1][0],ls[i-1][1]
        for h in range(H+1):
            if atk>=h:
                table[i][h]=min(table[i-1][h], cost)
            else:
                table[i][h]=min(table[i-1][h], table[i][h-atk]+cost)
    return(table[-1][-1])

print(dp(H,N,ls))

Solution (Python):
h,n=map(int,input().split())
l=[]
ans=0
for i in range(n):
    a,b=map(int,input().split())
    l.append((a,b))
d=[0]*10005
for i in range(h):
    for j in l:
        a,b=j[0],j[1]
        x=d[i]+b
        y=min(10004,i+a)
        if i==0 or (d[i]!=0 and d[y]==0):
            if d[y]==0:
                d[y]=x
            else:
                d[y]=min(d[y],x)
        elif d[i]!=0 and d[y]!=0:
            d[y]=min(d[y],x)

for i in range(h,10005):
    if ans==0:
        ans=d[i]
    elif d[i]!=0:
        ans=min(ans,d[i])
print(ans)

Solution (Python):

''':'
docker run --rm -it -v $(cd $(dirname $0) && pwd):/vo:ro pypy:3-2.4.0 \
   /bin/bash -c "pypy3 /vo/$(basename $0) < /vo/g.inp"
exit $?
'''
import sys
import math


def _ia():
    return [int(x) for x in sys.stdin.readline().strip().split()]


h, n = _ia()
ab = [_ia() for _ in range(n)]
m_max = math.ceil(h / ab[0][0]) * ab[0][1]
h1 = h + 1
dp = [
    [0] + [m_max + 1] * h for i in range(n + 1)
]
for i in range(n):
    ai, bi = ab[i]
    for j in range(1, h1):
        if j >= ai:
            dp[i + 1][j] = min(dp[i][j], dp[i][j - ai] + bi, dp[i + 1][j - ai] + bi)
        else:
            dp[i + 1][j] = min(dp[i][j], bi)
print(dp[n][h])

Solution (Python):
import sys
inputs = sys.stdin.readlines()

h, n = map(int, inputs[0].split())
AB = [tuple(map(int, s.split())) for s in inputs[1:]]

dp = [10 ** 9] * (h+1)
dp[0] = 0
for i in range(h):
    for a, b in AB:
        k = min(i + a, h)
        dp[k] = min(dp[k], dp[i] + b)
print(dp[h])

Solution (Python):
h,n=map(int,input().split())
ans=[10**10 for i in range(h+1)]+[0 for i in range(10**4)]
ans[0]=0
for i in range(n):
    a,b=map(int,input().split())
    tmp=0
    while tmp<=h:
        ans[tmp]=min(ans[tmp-a]+b,ans[tmp])
        tmp+=1
print(ans[h])

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

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

AB = []

for i in range(N):
	a,b = map(int, input().split())
	AB.append([a,b])
AB = np.array(AB)
A = AB[:,0]
B = AB[:,1]
dp = np.array([0]*(H+1))
for i in range(1, H+1):
	dp[i] = np.min(dp[np.maximum(i - A, 0)]+B)

print(dp[H])

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

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

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

DP = [1 << 32-1] * (H+10**4 + 10**4)
DP[0] = 0

for i in range(H+10**4):
    for a, b in AB:
        DP[i + a] = min(DP[i+a], DP[i] + b)

print(min(DP[H:]))

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

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

AB = []

for i in range(N):
	a,b = map(int, input().split())
	AB.append([a,b])
AB = np.array(AB)
A = AB[:,0]
B = AB[:,1]
dp = np.array([0]*(H+1))
for i in range(1, H+1):
	dp[i] = np.amin(dp[np.maximum(i - A, 0)]+B)

print(dp[H])

Solution (Python):
import sys
inputs = sys.stdin.readlines()

h, n = map(int, inputs[0].split())
AB = []
for s in inputs[1:]:
    a, b = map(int, s.split())
    AB.append((a, b))
AB.sort(key=lambda ab:ab[1])

dp = [10 ** 9] * (h+1)
dp[0] = 0
 
for i in range(h):
    for a, b in AB:
        k = min(i + a, h)
        dp[k] = min(dp[k], dp[i] + b)
print(dp[h])

Solution (Python):
INF=10**10
def main():
  H,N=map(int,input().split())
  AB=[]
  for i in range(N):
    AB.append(list(map(int,input().split())))
  dp=[INF]*(H+1)
  dp[0]=0
  for a,b in AB:
    for k in range(H+1):
      tmp=k-a
      if tmp<0:
        tmp=0
      need_magic=dp[tmp]+b
      if need_magic<dp[k]:
        dp[k]=need_magic
  print(dp[H])
main()

Solution (Python):
import numpy as np

H,N = list(map(int, input().split()))
As = []
Bs = []
for _ in range(N):
    a, b = list(map(int, input().split()))
    As.append(a)
    Bs.append(b)
As = np.array(As)
Bs = np.array(Bs)

dp = np.full((H+1), np.inf)
dp[0] = 0

for c in range(1,H+1):
    dp[c] = np.amin(dp[np.maximum(c - As, 0)] + Bs)

print(int(dp[-1]))

Solution (Python):


import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

h,n = LI()
dp = [inf]*(h+1)
dp[0] = 0
ab = [LI() for _ in range(n)]
for i in range(h+1):
    for a,b in ab:
        if i + a <= h:
            dp[i+a] = min(dp[i+a],dp[i]+b)
        else:
            dp[-1] = min(dp[-1],dp[i]+b)
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 = [0 for _ in range(H + 1)]
dp[0] = 0

def test_func(dp, A_list, B_list, i, N):
    return(min([(dp[i - A_list[j]] if i >= A_list[j] else 0) + B_list[j] for j in range(N)]))


for i in range(1, H + 1):
    dp[i] = test_func(dp, A_list, B_list, i, N)

print(dp[-1])

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

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

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

dp=[-1]*(h+maxA+5)
dp[0]=0
for i in range(1,h+maxA+5):
    for m in range(n):
        hp=M[m][0]
        mp=M[m][1]
        if i>=hp and dp[i-hp]!=-1: 
            if dp[i]==-1: 
                dp[i]=dp[i-hp]+mp
            else: 
                dp[i]=(min(dp[i],dp[i-hp]+mp))

chk=h
while dp[chk]==-1:
    chk+=1
ans=dp[chk]
for i in range(chk+1,h+maxA+5):
    if dp[i]!=-1:
        ans=min(ans,dp[i])
print(ans)

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

def dp(h,n,ls):
    table=[[0]*(h+1) for i in range(n)]
    atk,cost=ls[0][0],ls[0][1]
    for x in range(h+1):
        cost_of_this = cost*((x-1)//atk+1) if x!=0 else cost
        table[0][x]=cost_of_this
    for i in range(1,n):
        atk,cost=ls[i][0],ls[i][1]
        for j in range(h+1):
            if atk>=j:
                table[i][j]=min(table[i-1][j], cost)
            else:
                table[i][j]=min(table[i-1][j], table[i][j-atk]+cost)
    return(table[-1][-1])

ans=dp(h,n,ls)
print(ans)

Solution (Python):
H,N = map(int,input().split())
MAXH = H+10000
DP = [float("inf")]*MAXH
DP[0] = 0
for i in range(N):
    a,b = map(int,input().split())
    for j in range(MAXH-a):
        if j>H+a:break
        DP[j+a] = min(DP[j+a],DP[j]+b)
print(min(DP[H:]))

Solution (Python):
import sys
from collections import *
import heapq
import math
import bisect
from itertools import permutations,accumulate,combinations,product
from fractions import gcd
def input():
    return sys.stdin.readline()[:-1]
mod=10**9+7

h,n=map(int,input().split())
ab=[list(map(int,input().split())) for i in range(n)]
dp=[[float('inf')]*(h+1) for i in range(n+1)]
dp[0][0]=0

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

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

Solution (Python):
import sys
input = sys.stdin.readline
h, n = map(int, input().split())
ab = []
ma = 0
for i in range(n):
    a, b = map(int, input().split())
    ma = max(ma, a)
    ab.append([a, b])

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

for i, (a, b) in enumerate(ab):
    dp[i + 1][0] = 0
    for j in range(h + ma + 1):
        if j >= a:
            dp[i + 1][j] = min(dp[i + 1][j - a] + b, dp[i][j])
        else:
            dp[i+1][j] = min(dp[i+1][j], dp[i][j])

print(min(dp[n][h:]))

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

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

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

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

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

b,a = zip(*sorted(zip(b,a))) 
dp = [0]*(h+1)
dp[0] = 0
for i in range(1,h+1):
    dp[i] = 10**12
    for j in range(n):
        if i -a[j] >= 0:
            dp[i] = min(dp[i],dp[i-a[j]]+b[j])
        else: dp[i] = min(dp[i],b[j])
"""print(dp)
print(a,b)"""
print(dp[h])

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

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

dp=[10**30]*(10**4+1)

dp[hp]=0

for a,b in skills:
    for h in range(hp,0,-1):
        if h-a>=0:
            dp[h-a]=min(dp[h-a],dp[h]+b)
        else:
            dp[0]=min(dp[0],dp[h]+b)
            
print(dp[0])

Solution (Python):
H,N = map(int,input().split())
MAXH = H+10000
DP = [float("inf")]*MAXH
DP[0] = 0
for i in range(N):
    a,b = map(int,input().split())
    for j in range(MAXH):
        if j+a>MAXH-1:break
        DP[j+a] = min(DP[j+a],DP[j]+b)
print(min(DP[H:]))

Solution (Python):
H,N=map(int,input().split())
ABC=[]
for _ in range(N):
  a,b=map(int,input().split())
  ABC.append((a,b,a/b))
A=[ABC[i][0] for i in range(N)]
B=[ABC[i][1] for i in range(N)]
dp=[[float('inf')]*(H+1) for i in range(N+1)]
for i in range(N+1):
  dp[i][0]=0
  
for i in range(N):
  for j in range(1,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+1][0]+B[i])
print(dp[N][H])

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

Solution (Python):
H,N = map(int,input().split())
MAXH = H+1
DP = [float("inf")]*MAXH
DP[0] = 0
a = [0]*N
b = [0]*N
for i in range(N):
  a[i],b[i] = map(int,input().split())
for i in range(MAXH):
  if DP[i] == float("inf"):
    continue    
  for j in range(N):
        DP[min(i+a[j],H)] = min(DP[min(i+a[j],H)],DP[i]+b[j])
print(DP[H])

Solution (Python):

 
def main():
    h, n = map(int, input().split())
    ab = []
    for _ in range(n):
        ab.append(list(map(int, input().split())))
    
    inf = 100000000000
    
    damages = [inf for _ in range(100000)]
    damages[0] = 0
    pre_damage = -1
    for i in range(h):
        if damages[i] == inf:
            continue
        for j in range(n):
            new_damage = ab[j][0]
            if damages[i + new_damage] > damages[i] + ab[j][1]:
                damages[i + new_damage] = damages[i] + ab[j][1]
        
 
    print(min(damages[h:]))
main()

Solution (Python):
def calc_m_value(M, A, B, N, h):
    return min([M[h - A[i]]+B[i] if A[i] <= h else B[i] for i in range(N)])

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)

M = [0] * (H+1)
for i in range(1, H+1):
    M[i] = calc_m_value(M, A, B, N, i)

print(M[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 for i in range(H+1)]

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

print(dp[H])

Solution (Python):


def main():
    h, n = map(int, input().split())
    ab = []
    for _ in range(n):
        ab.append(list(map(int, input().split())))
    
    inf = 100000000000
    
    damages = [0] + [inf] * h
    for i in range(1, h + 1):
        for j in range(n):
            damage_monster = ab[j][0]
            damage_toki = ab[j][1]
            
            damages[i] = min(damages[max(0, i - damage_monster)] + damage_toki, damages[i])


    print(min(damages[h:]))
main()

Solution (Python):
import sys
import numpy as np
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)

H, N = map(int, readline().split())
AB = np.array([list(map(int,
                        readline().split())) for _ in range(N)],
              dtype=np.int64)

A = AB[:, 0]
B = AB[:, 1]

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

print(dp[H])

Solution (Python):
INF = 10 ** 18
H, N = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(N)]
dp = [INF for i in range(H + 1)]

dp[0] = 0

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

print(dp[-1])

Solution (Python):
import sys
def input():
    return sys.stdin.readline()[:-1]

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

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

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

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

Solution (Python):
H,N = map(int,input().split())
AB = []
 
for i in range(N):
    a,b = map(int,input().split())
    AB.append([a,b])
INF = 10**15
dp = [[INF]*(2*10**4+1) for i in range(N+1)]
for i in range(N+1):
    dp[i][0] = 0
 
for i in range(N):
    for j in range(1,2*10**4+1):
        dp[i+1][j] = min(dp[i][j],dp[i+1][j-AB[i][0]]+AB[i][1])
        
ans = float('inf')
for i in range(H,2*10**4+1):
    ans = min(ans,dp[N][i])
print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
h, n = map(int, input().split())
ab = []
ma = 0
for i in range(n):
    a, b = map(int, input().split())
    ma = max(ma, a)
    ab.append([a, b])
ab.sort(reverse=True)
INF = 10 ** 9
dp = [[INF for i in range(h + ma + 1)] for j in range(n+1)]
ans = INF
for i, (a, b) in enumerate(ab):
    dp[i + 1][0] = 0
    for j in range(a, h + ma + 1):
        
        dp[i + 1][j] = min(dp[i + 1][j - a] + b, dp[i][j])
        if j >= h:
            ans = min(ans, dp[i + 1][j])

print(ans)

Solution (Python):

H, N = list(map(int, input().split()))
ab_list = []
max_a = -float("inf")
for _ in range(N):
    a, b = list(map(int, input().split()))
    ab_list.append((a, b))
    max_a = max(max_a, a)

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

for i in range(1, N + 1):
    a, b = ab_list[i - 1]
    next_j = 0
    
    over_min_cost = float("inf")
    for j in range(H + 1):
        
        before_best_cost = dp_table[i - 1][j]
        dp_table[i][j] = min(dp_table[i][j], before_best_cost)
        
        if j - a >= 0:
            cost = dp_table[i - 1][j - a] + b
            min_cost = min(before_best_cost, cost)

            cost = dp_table[i][j - a] + b
            min_cost = min(min_cost, cost)

            dp_table[i][j] = min(dp_table[i][j], min_cost)

        if j + a > H:
            cost = dp_table[i - 1][j] + b
            dp_table[i][H] = min(dp_table[i][H], cost)
            cost = dp_table[i][j] + b
            dp_table[i][H] = min(dp_table[i][H], cost)
            dp_table[i][H] = min(dp_table[i][H], dp_table[i - 1][H])

ans = dp_table[-1][H]
print(ans)

Solution (Python):
def resolve():
    H,N=(int(i) for i in input().split())
    magics=[[int(i) for i in input().split()] for j in range(N)]
    mx=2**31
    dpt=[mx for i in range(H+1)]
    dpt[-1]=0
    for i in range(H,0,-1):
        
        current=dpt[i]
        if current> dpt[0]:
            continue
        for m in magics:
            dpt[max(0,i-m[0])]=min(dpt[max(0,i-m[0])],current+m[1])
    print(dpt[0])

if __name__ == "__main__":
    resolve()

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
from math import floor,ceil,sqrt,factorial,log
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from operator import itemgetter
from fractions import gcd
mod = 10 ** 9 + 7
 

def ii(): return int(sys.stdin.readline().rstrip()) 
def mii(): return map(int,sys.stdin.readline().rstrip().split())
def limii(): return list(mii()) 
def lin(n:int): return [ii() for _ in range(n)]
def llint(n: int): return [limii() for _ in range(n)]

def ss(): return sys.stdin.readline().rstrip() 
def mss(): return sys.stdin.readline().rstrip()
def limss(): return list(mss()) 
def lst(n:int): return [ss() for _ in range(n)]
def llstr(n: int): return [limss() for _ in range(n)]

h,n = mii()
ab = llint(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])

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

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



INF=float("inf")

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

for aa,bb in zip(a,b):
    for hh in range(h,0,-1):
        if hh-aa>=0:
            dp[hh-aa]=min(dp[hh-aa],dp[hh]+bb)
        else:
            dp[0]=min(dp[0],dp[hh]+bb)
            
print(dp[0])

Solution (Python):

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

inf = 10**9
dp = [inf]*(h+1)
dp[0] = 0
for i in range(n):
    for j in range(h+1):
        d = min(j+ab[i][0], h)
        dp[d] = min(dp[d], dp[j]+ab[i][1])

res = dp[h]
print(res)

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

AB = []
for i in range(N):
    tmp = list(map(int, input().split()))
    AB.append(tmp)
    
dp = [10**9] * (H+1)
dp[0] = 0
    
for i in range(N):
    for j in range(H+1):
        a, b = AB[i]
        if j < a:
            dp[j] = min(dp[0]+b, dp[j])
        else:
            dp[j] = min(dp[j-a]+b, dp[j])
    
print(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 = [[10**9] * (H + 1) for _ in range(N + 1)]
for x in range(N + 1):
    dp[x][0] = 0
    

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




print(dp[N][H])

Solution (Python):
h, n = map(int, input().split())
a = []
b = []
for _ in range(n):
    ai, bi = map(int, input().split())
    a.append(ai)
    b.append(bi)
 
dp = [float("inf")] * (2 * 10000 + 1)
dp[0] = 0
for i in range(h):
    for j in range(n):
        if (i + a[j]) > 2 * 10000:
            dp[2 * 10000] = min(dp[2 * 10000], dp[i] + b[j])
            continue
        dp[i + a[j]] = min(dp[i + a[j]], dp[i] + b[j])
 
ans = float('inf')
for j in range(h, 2 * 10000 + 1):
    ans = min(ans, dp[j])
print(ans)

Solution (Python):
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate
import sys
import bisect
import string
import math
import time


def I(): return int(input())


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


def S(): return input()


def MS(): return map(str, input().split())


def LI(): return [int(i) for i in input().split()]


def LI_(): return [int(i)-1 for i in input().split()]


def StoI(): return [ord(i)-97 for i in input()]


def ItoS(nn): return chr(nn+97)


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


def show(*inp, end='\n'):
    if show_flg:
        print(*inp, end=end)


YN = {False: 'No', True: 'Yes'}
MOD = 10**9+7
inf = float('inf')
IINF = 10**10
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']


show_flg = True
show_flg = False


def main():
    H, N = MI()
    A = [0] * N
    B = [0] * N
    dp = [[10**12 for i in range(H+1)]
          for i in range(N+1)]
    

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

    for i in range(N):
        A[i], B[i] = MI()
        

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

    print(dp[N][-1])


if __name__ == '__main__':
    main()

Solution (Python):
h,n = map(int, input().split( ))
m = []
mxa = 0
for _ in range(n):
    ai,bi = map(int, input().split( ))
    m.append((ai,bi))
    mxa = max(mxa,ai)
inf = 10**10
dp = [inf for _ in range(h+1+mxa)]
dp[0] = 0
for i in range(h+mxa):
    for j in range(n):
        if i+m[j][0]<=h+mxa:
            dp[i+m[j][0]] = min(dp[i+m[j][0]],dp[i]+m[j][1])
print(min(dp[h:]))