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

from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI1(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    return res[:-1] if res[-1] == "\n" else res
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
dire = [[1, 0], [0, 1], [-1, 0], [0, -1]]
MOD = 1000000007

def main():
    H, N = LI()
    AB = LIR(N)

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

    for a, b in AB:
        for i in range(H+1):
            ni = min(H, a + i)
            nv = dp[i] + b
            if nv < dp[ni]:
                dp[ni] = nv

    print(dp[H])


main()

Solution (Python):
min2 = lambda x,y: x if x < y else y
H,N = map(int,input().split())


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

for _ in range(N):
    a,b = map(int,input().split())
    for i,v in enumerate(dp):
        j = min2(H,i+a)
        dp[j] = min2(dp[j],v+b)

print(dp[-1])

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

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

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

Solution (Python):
import sys
readline = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7

INF = 10**18
eps = 10**-7


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

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

for i in range(N):
    w,v = map(int,readline().split())
    
    for j in range(W+1):
        dp[j] = min(dp[j],dp[max(j-w,0)] + v)

print(dp[W])

Solution (Python):
import sys
readline = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7

INF = 10**18
eps = 10**-7


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

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

for i in range(N):
    w,v = map(int,readline().split())
    
    for j in range(W+1):
        dp[j] = min(dp[j],dp[max(j-w,0)] + v)

print(dp[W])

Solution (Python):
import sys
readline = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7

INF = 10**18
eps = 10**-7


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

dp = [INF for j in range(W+1)]
dp[0] = 0

for i in range(N):
    w,v = map(int,readline().split())
    
    for j in range(W+1):
        dp[j] = min(dp[j],dp[max(j-w,0)] + v)

print(dp[W])

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


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

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

print(dp[h])

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

A = []
B = []

for n in range(N):
  a, b = map(int, input().split())
  A.append(a)
  B.append(b)
  
INF = float('inf')
dp = [INF] * (H + max(A))
dp[0] = 0


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

print(dp[H])

Solution (Python):
import sys

def main(args):
    h, n = map(int,input().split())
    
    magic = [0]*n
    maxim = 0
    for i in range(n):
        dam, mp = map(int,input().split())
        magic[i] = (dam, mp)
        maxim = max(maxim, dam)
    
    damage = [float('inf')]*(2*10**4)
    damage[0] = 0
    for i in range(max(2*h, 2*maxim)):
        for m in magic:
            dam, mp = m
            damage[i] = min(damage[i-dam]+mp, damage[i])
    
    print(min(damage[h:]))

if __name__ == '__main__':
    main(sys.argv[1:])

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
INF = 10**9


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

print(dp[-1])

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

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


def main():
  H, N = list(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 j in range(H+1):
    dp[j] = float('inf')
  dp[0] = 0

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

  
  
  print(dp[H])


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

Solution (Python):
h,n = map(int,input().split())
magic = [ list(map(int,input().split())) for i in range(n)]
INF = float("inf")

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

"""
i番目までの魔法の中から攻撃力の合計が
jを超えるように選んだときの消費精神力の最小値
"""

for i in range(n):
    for j in range(h):
        if j < magic[i][0]:
             dp[i+1][j+1] = min(dp[i][j+1],magic[i][1])
        elif j >= magic[i][0] and 0<= j+1-magic[i][0] <= h:
            dp[i+1][j+1] = min(dp[i][j+1],dp[i][j+1-magic[i][0]]+magic[i][1],dp[i+1][j+1-magic[i][0]]+magic[i][1])
        
print(dp[n][h])

Solution (Python):
import math

H, N = 9, 3
ARR = [
    [8, 3],
    [4, 2],
    [2, 1]
]

H, N = 100, 6
ARR = [
    [1, 1],
    [2, 3],
    [3, 9],
    [4, 27],
    [5, 81],
    [6, 243],
]


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


def calculate(h, n, arr):
    brr = [math.inf] * (h + 1)

    brr[0] = 0

    for i in range(h + 1):
        for j in range(n):
            damage = arr[j][0]
            cost = arr[j][1]

            nextDamage = min(i + damage, h)
            nextCost = min(brr[nextDamage], brr[i] + cost)

            brr[nextDamage] = nextCost

    print(brr[-1])


calculate(H, N, ARR)

Solution (Python):
import math

H,N = map(int,input().split())
ARR = [list(map(int,input().split())) for i in range(N)]
def calculate(h, n, arr):

    brr = [math.inf] * (h + 1)

    brr[0] = 0
    for i in range(h + 1):
        for j in range(n):
            damage = arr[j][0]
            cost = arr[j][1]

            nextDamage = i + damage

            if nextDamage > h:
                nextDamage = h

            nextCost = min(brr[nextDamage], brr[i] + cost)
            brr[nextDamage] = nextCost

    print(brr[-1])

calculate(H, N, ARR)

Solution (Python):
import math




















H, N = map(int, input().split())
ARR = []

for i in range(N):
    ARR.append(list(map(int, input().split())))


def calculate(h, n, arr):
    brr = [math.inf] * (h+1)
    brr[0] = 0

    for i in range(h + 1):
        for j in range(n):

            damage = arr[j][0]
            cost = arr[j][1]

            nextDamage = i + damage

            if nextDamage > h:
                nextDamage = h

            nextCost = min(brr[i] + cost, brr[nextDamage])

            brr[nextDamage] = nextCost

    print(brr[-1])


calculate(H, N, ARR)

Solution (Python):
H, N = map(int, input().split())
AB = []
INF = 10**8 + 1

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

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

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

print(dp[-1])

Solution (Python):
import sys

read = sys.stdin.read
INF = 1 << 60


def main():
    H, N, *AB = map(int, read().split())

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

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

    print(dp[H])
    return


if __name__ == '__main__':
    main()

Solution (Python):
import sys

read = sys.stdin.buffer.read
INF = 1 << 60


def main():
    H, N, *AB = map(int, read().split())

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

    for a, b in zip(*[iter(AB)] * 2):
        for i in range(H + 1):
            if dp[i] > dp[max(i - a, 0)] + b:
                dp[i] = dp[max(i - a, 0)] + b

    print(dp[H])
    return


if __name__ == '__main__':
    main()

Solution (Python):
import sys

read = sys.stdin.buffer.read
INF = 1 << 60


def main():
    H, N, *AB = map(int, read().split())

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

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

    print(dp[H])
    return


if __name__ == '__main__':
    main()

Solution (Python):
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    H, N, *AB = map(int, read().split())

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

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

    print(dp[H])
    return


if __name__ == '__main__':
    main()

Solution (Python):
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    H, N, *AB = map(int, read().split())

    magic = [0] * N
    for i, (a, b) in enumerate(zip(*[iter(AB)] * 2)):
        magic[i] = (a, b)

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

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

    print(dp[N][H])
    return


if __name__ == '__main__':
    main()

Solution (Python):
def main():
    INF = 10 ** 10
    H, N = list(map(int, input().split(' ')))
    magic = [list(map(int, input().split(' '))) for _ in range(N)]
    MAX_A = max(list(map(lambda x: x[0], magic)))
    dp = [INF for _ in range(MAX_A + H + 1)]
    dp[0] = 0
    for h in range(1, MAX_A + H + 1):
        for i in range(N):
            a, b = magic[i]
            if h - a < 0:
                continue
            dp[h] = min(dp[h], b + dp[h - a])
    print(min(dp[H:]))


if __name__ == '__main__':
    main()

Solution (Python):
H,N = map(int,input().split())
Q = []
for _ in range(N):
    a,b = map(int,input().split())
    Q.append((a,b))
INF = float("inf")
dp = [INF]*(H+1)
dp[0] = 0
for i in range(H+1):
    for a,b in Q:
        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[-1])

Solution (Python):



from fractions import gcd
from itertools import combinations,permutations,accumulate 

from collections import deque,defaultdict,Counter
import decimal
import re











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

def readInts():
  return list(map(int,input().split()))
def I():
  return int(input())
H,n = readInts()
A = []
B = []
for i in range(n):
    a,b = readInts()
    A.append(a)
    B.append(b)


INF = float('inf')
dp = [INF] * (H+1)
dp[0] = 0
for h in range(0,H+1):
    for i in range(n):
        dp[min(h+A[i],H)] = min(dp[min(h+A[i],H)], dp[h] + B[i])


print(dp[H])

Solution (Python):
import numpy as np

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

aa = np.array(la)
ab = np.array(lb)
maxa = np.max(aa)


min_magic = np.zeros(maxa + h + 1, int)

for i in range(1, h + 1):
    min_magic[maxa + i] = np.min(min_magic[maxa + i - la] + lb)

answer = min_magic[maxa + h]
print(answer)

Solution (Python):
import numpy as np

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)
  
A = np.array(A)
B = np.array(B)
DP = np.zeros(H + 1)

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

print(int(DP[-1]))

Solution (Python):
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)
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):
    dp[i+1][j]=min(dp[i+1][j],dp[i][j])    
    dp[i+1][min(j+a[i],h)]=min(dp[i+1][j]+b[i],dp[i+1][min(j+a[i],h)])
print(dp[n][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())

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

if __name__ == "__main__":
    main()

Solution (Python):

from collections import deque, Counter
from heapq import heappop, heappush
from bisect import bisect_right

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

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

if __name__ == "__main__":
    main()

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

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

max_d = max(a for a,b in ab_input)

dp =[0]*(h+max_d)
for i in range(1,h+max_d):
    dp[i]=min(dp[i-a]+b for a,b in ab_input)

print(dp[h])

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

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

max_d = max(a for a,b in ab_input)

dp =[0]*(h+max_d)
for i in range(1,h+max_d):
    dp[i]=min(dp[i-a]+b for a,b in ab_input)

print(dp[h])

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

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

max_d = max(a for a,b in ab_input)

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

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

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

max_d = max(a for a,b in ab_input)

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

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

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

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




dp=[[10**10 for _ in range(h+1)]for _ in range(n+1)]
dp[0][0]=0
for i in range(0,n):
  damage = magics[i][0]
  cost = magics[i][1]
  for j in range(0,h+1):
    dp[i+1][j] = min( dp[i+1][j], dp[i][j] )

    to = min( j+damage, h )
    dp[i+1][to] = min( dp[i+1][j]+cost, dp[i+1][to] )
                                                 
print(dp[n][h])

Solution (Python):
def solve():
    H, N = map(int, input().split())
    A = [list(map(int, input().split())) for _ in range(N)]
    dp = [float('inf')]*(H+10**4)
    dp[0] = 0
    for h in range(1,H+10**4):
        for i in range(N):
            if A[i][0]<=h:
                dp[h] = min(dp[h],dp[h-A[i][0]]+A[i][1])
    ans = min(dp[H:])
    return ans
print(solve())

Solution (Python):
H, N = map(int, input().split())
dp = [10 ** 9] * (H + 1)
dp[0] = 0
for _ in range(N):
    a, b = map(int, input().split())
    for i in range(H):
        idx = min(H, i + a)
        dp[idx] = min(dp[idx], dp[i] + b)
print(dp[H])

Solution (Python):
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


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

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

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


dp = [10**9 for i in range((h+1)+10000)]
dp[0] = 0
for i in range(1, (h+1)+10000):
  for j in range(n):
    a, b = ab[j]
    if a > i:
      continue
    dp[i] = min(dp[i], dp[i-a]+b)

x = min(dp[h:])
print (x)

Solution (Python):
def main():
	inf=10**9
	h,n=map(int,input().split())
	ab=[]
	r=0
	for i in range(n):
		a,b=map(int,input().split())
		ab.append((a,b))
		r=max(r,a)
	
	dp=[[inf for _ in range(r+h)]for _ in range(n+1)]
	for i in range(n+1):
		dp[i][0]=0
	for i in range(n):
		for j in range(r+h):
			if j-ab[i][0]>=0:
				dp[i+1][j]=dp[i+1][j-ab[i][0]]+ab[i][1]
			dp[i+1][j]=min(dp[i][j],dp[i+1][j])
	ans=inf
	for i in range(r):
		ans=min(ans,dp[n][i+h])
	print(ans)
if __name__ == '__main__':
	main()

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

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

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

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

Solution (Python):
import numpy as np
h,n=map(int,input().split())
p=[list(map(int,input().split())) for _ in range(n)]
m=10**4
dp=[0]*(h+m+1)
for i in range(m+1,h+m+1):
  dp[i]=min(dp[i-a]+b for a,b in p)
print(dp[h+m])

Solution (Python):
H,N = map(int,input().split())
AB  = [list(map(int,input().split())) for i in range(N)]
inf = float("inf")
maxA = max(AB)[0]
dp = [inf]*(maxA+H)
dp[0]=0

for i in range(N):
  a,b = map(int,AB[i])
  for j in range(H+maxA):
    if j-a>=0:
      dp[j] = min(dp[j-a] + b, dp[j])

print(min(dp[H:]))

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

def solve():
    INF = float('inf')

    def min2(x, y): return x if x <= y else y

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

    items.sort()

    dp = [INF] * (H+1)
    dp[0] = 0
    for vi, wi in items:
        for j in range(H-vi+1):
            dp[j+vi] = min2(dp[j+vi], dp[j]+wi)
        for j in range(max(0, H-vi+1), H+1):
            dp[H] = min2(dp[H], dp[j]+wi)


    print(dp[H])


solve()

Solution (Python):
H, N = map(int, input().split())
A = []
max_A = 0
for i in range(N):
    A.append(tuple(map(int, input().split())))
    max_A = max(max_A, A[i][0])

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

for i in range(2 * 10 ** 4):
    for a, b in A:
        if i + a <= 2 * 10 ** 4:
            dp[i+a] = min(dp[i]+b, dp[i+a])

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 = [10**9]*(h+1)
dp[0] = 0
for i in range(h):
    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):
H,N = map(int,input().split())
Magic = [list(map(int, input().split())) for i in range(N)]

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

for i in range(N):
    a,b = Magic[i]
    for h in range(H):
        
        next_h = min(h+a,H)
        dp[next_h]=min(dp[next_h],dp[h]+b)

print(dp[-1])

Solution (Python):
h,n = map(int,input().split())
a = [0]*n
for i in range(n):
    a[i] = list(map(int,input().split()))
dp = [float("Inf")]*(h+1)
dp[0] = 0
for i in range(h):
    for A,B in a:
        dp[min(i+A,h)] = min(dp[min(i+A,h)],dp[i]+B)
print(dp[-1])

Solution (Python):
import sys
readline = sys.stdin.readline
INF = 10 ** 8


def main():
    H, N = map(int, readline().rstrip().split())
    dp = [INF] * (H + 1)  
    dp[0] = 0

    for _ in range(N):
        hp, mp = map(int, readline().rstrip().split())

        for i in range(H):
            j = min(i+hp, H)
            dp[j] = min(dp[j], dp[i] + mp)

    print(dp[-1])


if __name__ == '__main__':
    main()

Solution (Python):
import sys
import heapq
import re
from itertools import permutations
from bisect import bisect_left, bisect_right
from collections import Counter, deque
from math import factorial, sqrt, ceil, gcd
from functools import lru_cache, reduce
from decimal import Decimal
INF = 1 << 60
MOD = 1000000007
sys.setrecursionlimit(10 ** 7)


class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

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

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

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

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


def dijkstra_heap(s, edge, n):
    
    d = [10**20] * n
    used = [True] * n 
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist,a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d


def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr


def lcm(x, y):
    return (x * y) // gcd(x, y)


def lcm_list(numbers):
    return reduce(lcm, numbers, 1)


def gcd_list(numbers):
    return reduce(gcd, numbers)


def is_prime(n):
    if n <= 1:
        return False
    p = 2
    while True:
        if p ** 2 > n:
            break
        if n % p == 0:
            return False
        p += 1
    return True



def eratosthenes(limit):
    A = [i for i in range(2, limit+1)]
    P = []

    while True:
        prime = min(A)
        
        if prime > sqrt(limit):
            break
            
        P.append(prime)
            
        i = 0
        while i < len(A):
            if A[i] % prime == 0:
                A.pop(i)
                continue
            i += 1
            
    for a in A:
        P.append(a)
            
    return P


def permutation_with_duplicates(L):

    if L == []:
        return [[]]

    else:
        ret = []

        
        S = sorted(set(L))

        for i in S:

            data = L[:]
            data.remove(i)

            for j in permutation_with_duplicates(data):
                ret.append([i] + j)

        return ret



h, n = map(int, input().split())
a = [0 for i in range(n)]
b = [0 for i in range(n)]
for i in range(n):
    a[i], b[i] = map(int, input().split())
dp = [INF for i in range(h)]
dp[0] = 0 
ans = INF
for i in range(h):
    for j in range(n):
        if i + a[j] < h:
            dp[i + a[j]] = min(dp[i + a[j]], dp[i] + b[j])
        else:
            ans = min(ans, dp[i] + b[j])
print(ans)

Solution (Python):
import sys, os, math, bisect, itertools, collections, heapq, queue

from decimal import Decimal
from collections import defaultdict



sys.setrecursionlimit(10000000)

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)


MOD = 10 ** 9 + 7
MAX = float('inf')


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

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

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


if __name__ == '__main__':
    main()

Solution (Python):
def main():
    Hit,N = map(int, input().split())
    A = [0]*N
    B = [0]*N
    H = [-1]*(10**5+10000)
    mi = 10**10
    for i in range(N):
        A[i] ,B[i] = map(int, input().split())
    for i in range(N):
        H [A[i]] = B[i] if H[A[i]] == -1 else min(H [A[i]],B[i])
        if A[i] >= Hit:
            mi = min(mi,B[i])
        for j in range(Hit+1):
            if H[j]!=-1:
                H[j+A[i]] = B[i] + H[j] if H[j+A[i]] == -1 else min(H[j+A[i]],B[i]+H[j])
                if j+A[i] >= Hit:
                    mi = min(mi,B[i] + H[j])
    print(mi)






if __name__ == '__main__':
    main()

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

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

Solution (Python):
H, N = map(int, input().split())
INF = float('inf')
dp = [INF]*(H+1) 
ans = 0
for n in range(N):
    a,b = map(int, input().split())
    for h in range(1, H + 1):
        if a >= h:
            dp[h] = min(dp[h], b)
        else:
            dp[h] = min(dp[h], dp[h-a] + b)

print(dp[H])

Solution (Python):
import sys
sys.setrecursionlimit(10**7) 
import math
from copy import copy, deepcopy
from copy import deepcopy as dcp
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right

from collections import deque


from collections import Counter

from itertools import accumulate,combinations,permutations

from heapq import heapify,heappop,heappush


from functools import lru_cache

from decimal import Decimal

def input(): 
    x=sys.stdin.readline()
    return x[:-1] if x[-1]=="\n" else x
def printl(li): _=print(*li, sep="\n") if li else None
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]
def main():
    mod = 1000000007
    

    
    H,N = map(int, input().split())
    
    
    S = tuple(tuple(map(int, input().split())) for i in range(N)) 
    inf=10**9
    dp=[inf]*(H+1)
    dp[0]=0
    for A,B in S:
        for i in range(0,H):
            dp[min(i+A,H)]=min(dp[i]+B,dp[min(i+A,H)])
    print(dp[-1])




if __name__ == "__main__":
    main()

Solution (Python):
H, N, *AB = map(int, open(0).read().split())
A = AB[::2]
B = AB[1::2]

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

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

Solution (Python):
H, N, *AB = map(int, open(0).read().split())
A = []
B = []
for a, b in zip(*[iter(AB)] * 2):
    A.append(a)
    B.append(b)

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

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

Solution (Python):
import sys
import itertools

import time
import math
 
sys.setrecursionlimit(10 ** 7)
 
from collections import defaultdict
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

H, N = map(int, readline().split())
A = [0] * N
B = [0] * N

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

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