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

dp[0] = 0

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


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

min_mp = 10**9
for i in range(N):
    if min_mp > AB[i][1]:
        min_mp = AB[i][1]
        min_mp_i = i

for h in range(1,min(AB[min_mp_i][0],H)+1):
    
    DP[h] = min_mp

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

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):
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):
inf = 10 ** 18
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 = [inf] * (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):



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)
AB.sort(key=lambda a_b: -a_b[0] * 1.0 / a_b[1])

a0, b0 = AB[0]
dp = [0] + [float('inf')] * (H + a0)

cur = 0
while cur <= H + a0:
    dp[cur] = cur // a0 * b0
    cur += a0


for a, b in AB[1:]:
    for i in range(a, H + a0 + 1):
        dp[i] = min(dp[i], dp[i - a] + b)
print(min(dp[H:]))

Solution (Python):



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

H, N = gets()
AB = getss(N)
AB.sort(key=lambda a_b: -a_b[0] * 1.0 / a_b[1])

a0, b0 = AB[0]
dp = [0] + [float('inf')] * (H + a0)

cur = 0
while cur <= H + a0:
    dp[cur] = cur // a0 * b0
    cur += a0


for a, b in AB[1:]:
    for i in range(a, H + a0 + 1):
        dp[i] = min(dp[i], dp[i - a] + b)
print(min(dp[H:]))

Solution (Python):




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

H, N = gets()
AB = getss(N)
AB.sort(key=lambda a_b: -a_b[0] * 1.0 / a_b[1])

a0, b0 = AB[0]
dp = [0] + [float('inf')] * (H + a0)

cur = 0
while cur <= H + a0:
    dp[cur] = cur / a0 * b0
    cur += a0


for a, b in AB[1:]:
    for i in xrange(a, H + a0 + 1):
        dp[i] = min(dp[i], dp[i - a] + b)
print min(dp[H:])

Solution (Python):

import sys


def solve(H: int, N: int, A: "List[int]", B: "List[int]"):
    hmax = H + max(A)
    cost = [0] * hmax
    magics = [(a, b) for a, b in zip(A,B)]
    for i in range(1, hmax):
        for a, b in magics:
            if i >= a:
                cost[i] = min(cost[i-a]+b, cost[i]) if cost[i] > 0 else cost[i-a]+b
            else:
                cost[i] = min(b, cost[i]) if cost[i] > 0 else b
    
    print(min(cost[H:]))

def solve_dijkstra(H: int, N: int, A: "List[int]", B: "List[int]"):
    nodes = {0: 0}
    fixed = 0
    unfixed = set()
    while True:
        cost = nodes[fixed]
        for a, b in zip(A,B):
            new_node = fixed + a
            last = nodes.get(new_node, 999999999)
            new_cost = cost + b
            if last > new_cost:
                nodes[new_node] = new_cost
                unfixed.add(new_node)
        fixed = min(unfixed)
        if fixed >= H:
            break
        unfixed.remove(fixed)
    print(min([v for k, v in nodes.items() if k >= H]))


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    H = int(next(tokens))  
    N = int(next(tokens))  
    A = [int()] * (N)  
    B = [int()] * (N)  
    for i in range(N):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
    solve(H, N, A, B)

if __name__ == '__main__':
    main()

Solution (Python):
import sys

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

dp = [0] * (H + 1)

for i in range(1, H + 1):
    dp[i] = min(dp[max(i - damage, 0)] + cost for damage, cost in magic)

ans = dp[H]

print(ans)

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

    mxA = 10 ** 4
    dp = [[10**15 for i in range(h+1+mxA)] for i in range(n+1)]

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

    for i in range(n):
        for sum_dam in range(h+1+mxA):
            if sum_dam-l[i][0]>=0:
                dp[i+1][sum_dam] = min(dp[i+1][sum_dam],  \
                                dp[i][sum_dam - l[i][0]] + l[i][1],  \
                                dp[i+1][sum_dam-l[i][0]] + l[i][1])
            dp[i+1][sum_dam] = min(dp[i+1][sum_dam], dp[i][sum_dam])

    print(min(dp[-1][h:h+mxA+1]))

if __name__ == '__main__':
    solve()

Solution (Python):
h,n=map(int,input().split())
mahou=[list(map(int,input().split())) for i in range(n)]
INF=10**10
dp=[INF]*(h+1)
dp[0]=0
for hp in range(h+1):
  for use in mahou:
    dp[hp]=min(dp[max(0,hp-use[0])]+use[1],dp[hp])
print(dp[h])

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, floor
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

H, N = MAP()
temp = [LIST() for _ in range(N)]
temp = [list(x) for x in zip(*temp)]
A, B = temp[0], temp[1]

DP = [[INF]*(H + max(A) + 1) for _ in range(N + 1)]
DP[0][0] = 0
a = max(A)

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

print(min(DP[N][H:H + max(A) + 1]))

Solution (Python):

import sys


def solve(H: int, N: int, A: "List[int]", B: "List[int]"):
    nodes = {0: 0}
    fixed = 0
    unfixed = set()
    while True:
        cost = nodes[fixed]
        for a, b in zip(A,B):
            new_node = fixed + a
            last = nodes.get(new_node, 999999999)
            new_cost = cost + b
            if last > new_cost:
                nodes[new_node] = new_cost
                unfixed.add(new_node)
        fixed = min(unfixed)
        if fixed >= H:
            break
        unfixed.remove(fixed)
    print(min([v for k, v in nodes.items() if k >= H]))


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    H = int(next(tokens))  
    N = int(next(tokens))  
    A = [int()] * (N)  
    B = [int()] * (N)  
    for i in range(N):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
    solve(H, N, A, B)

if __name__ == '__main__':
    main()

Solution (Python):
def solve():
    H,N = map(int, input().split())
    
    ABs = [list(map(int, input().split())) for _ in range(N)]
    
    dp_table = [[0]*(H+1) for _ in range(N+1)]
    
    for j in range(1,H+1): dp_table[0][j] = 10**9
    
    for i in range(N):
        for j in range(H+1):
            if j-ABs[i][0]<0:
                dp_table[i+1][j] = min(dp_table[i][j], ABs[i][1])
            else:
                dp_table[i+1][j] = min(dp_table[i][j], dp_table[i+1][j-ABs[i][0]]+ABs[i][1])
                
    print(dp_table[N][H])
    
solve()

Solution (Python):
def main():
    INF = 10**9
    H,N = map(int,input().split())
    AB = [list(map(int,input().split())) for _ in range(N)]
    maxA = max(A for A,B in AB)
    dp = [INF]*(H+maxA)
    dp[0] = 0
    for i in range(1,H+maxA):
        dp[i] = min(dp[i-A]+B for A,B in AB)
    print(min(dp[H:]))


if __name__ == '__main__':
    main()

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


if __name__ == '__main__':
    main()

Solution (Python):
def main():
    INF = float('inf')
    H,N = map(int,input().split())
    AB = [list(map(int,input().split())) for _ in range(N)]
    maxA = max(A for A,B in AB)
    dp = [INF]*(H+maxA)
    dp[0] = 0
    for i in range(H+maxA):
        if i <= 0:
            dp[i] = 0
        else:
            dp[i] = min(dp[i-A]+B for A,B in AB)
    print(min(dp[H:]))

if __name__ == '__main__':
    main()

Solution (Python):
import numpy as np 

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

A,B = np.array([list(map(int,input().split())) for i in range(N)]).T

dp = np.zeros(H+1,dtype=np.int32)

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

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,dtype=np.int32)

for i in range(1,H+1):
    dp[i] = np.amin(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 i in range(N)]

M = max(a for a,b in AB)

dp = [0]*(H+M)

for i in range(1,H+M):
    dp[i] = min(dp[i-a]+b for a,b in AB)
    
print(min(dp[H:]))

Solution (Python):
from sys import stdin




























def get_result(data):
    
    H, N = data[0]
    A_and_B = data[1:]
    A = [0 for _ in range(N)]
    B = [0 for _ in range(N)]
    for i in range(N):
        Ai, Bi = A_and_B[i]
        A[i] = Ai
        B[i] = Bi

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

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

    return dp[H]

if __name__ == '__main__':
    raw_data = [val.rstrip('\n') for val in stdin.readlines()]
    data = [list(map(int, val.split(' '))) for val in raw_data]
    result = get_result(data)
    print(result)

Solution (Python):
"""
前処理
"""
import numpy as np
H, N = map(int, input().split())
A = []
B = []
for _ in range(N):
    ai, bi = map(int, input().split())
    """
    入力したものをそれぞれリストに格納していく、これは真似ていこう
    """
    A.append(ai)
    B.append(bi)

"""
配列に変換
"""
A = np.array(A)
B = np.array(B)

"""
処理
"""

dp = np.zeros(H+1, dtype=np.int64)
dp[0] = 0

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

"""
output
"""
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 a,b in AB:
  for i in range(h):
    if i+a>=h:
      dp[h]=min(dp[h],dp[i]+b)
    else:
      dp[i+a]=min(dp[i+a],dp[i]+b)
print(dp[h])

Solution (Python):

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

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

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

print(dp[H])

Solution (Python):

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

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

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

print(dp[H])

Solution (Python):
h, n = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(n)]
dp = [1 << 31] * (h + 10**4)
dp[0] = 0
for i in range(h):
    for a, b in AB:
        dp[i + a] = min(dp[i + a], dp[i] + b)
print(min(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
input = sys.stdin.readline

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

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

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

Solution (Python):
import sys
input = sys.stdin.buffer.readline
 
h,n = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(n)]

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

for a,b in AB:
    for i in range(h):
        if dp[i]!=float("inf"):
            dp[min(i+a,h)]=min(dp[min(i+a,h)],dp[i]+b)
print(dp[-1])

Solution (Python):

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

INF=10**9

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

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


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


print(dp[N][H])

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

  return a

def chmax(a, b):
  if (a < b):
    return b

  return a

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

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

for n in range(N):
  for h in range(0, H+1):
    dp[n+1][h] = chmin(dp[n+1][h], dp[n][h])
    dp[n+1][min(h+li[n][0], H)] = chmin(dp[n+1][min(h+li[n][0], H)], dp[n+1][h]+li[n][1])

print(dp[N][H])

Solution (Python):
"""
前処理
"""
import numpy as np
H, N = map(int, input().split())
A = []
B = []
for _ in range(N):
    ai, bi = map(int, input().split())
    """
    入力したものをそれぞれリストに格納していく、これは真似ていこう
    """
    A.append(ai)
    B.append(bi)

"""
配列に変換
"""
A = np.array(A)
B = np.array(B)

"""
処理
"""

dp = np.zeros(H+1, dtype=np.int64) 
dp[0] = 0

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

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

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


a_max = max(a for a, b in ab)

dp = [0]*(h + a_max)

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

print(min(dp[h:]))

Solution (Python):
n,m=map(int, input().split())
s=[list(map(int, input().split())) for i in range(m)]
x=max(a for a,b in s)
dp=[0]*(n+x)
for i in range(0,n+x):
  if i>0:
    dp[i]=min(dp[i-a]+b for a,b in s)
print(min(dp[n:]))

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())
m = []
for i in range(n):
    ai,bi = map(int,input().split())
    m.append((ai,bi))

INF = 1000100001001

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


print(dp[n ][h])

Solution (Python):
import sys

read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
inputs = sys.stdin.buffer.readlines







def main():
	h,n=map(int,input().split())
	AB=[list(map(int,input().split())) for _ in range(n)]
	
	li=[10**10]*(10**5)
	li[0]=0
	
	for i in range(h):
		if li[i]==10**10:
			continue
		else:
			for a,b in AB:
				li[i+a]=min(li[i+a],li[i]+b)
	
	print(min(li[h:]))
	
	
	
	
	
	

if __name__ == "__main__":
	main()

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

H,N = imn()
AB = [iln() for _ in range(N)]
MAX_H = 10**4+1
dp = [10**10 for _ in range(MAX_H)]
dp[0] = 0

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

Solution (Python):
H, N = map(int, input().split())
A = [None] * N
B = [None] * N

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

lim = H + max(A)
dp = [10**8] * lim
dp[0] = 0

for h in range(lim):
    for n in range(N):
        rem = h - A[n]
        cns = B[n]

        if 0 < rem:
            cns += dp[rem]
        dp[h] = min(cns, dp[h])

print(min(dp[H:lim]))

Solution (Python):



def main():
    h, n = map(int, input().split())
    a = [0 for _ in range(n)]
    b = [0 for _ in range(n)]
    inf = float('inf')
    dp = [inf for _ in range(2 * 10 ** 4 + 100)]
    dp[0] = 0

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

    for i in range(h):
        for j, ai in enumerate(a):
            if dp[i] == inf:
                continue

            dp[i + ai] = min(dp[i + ai], dp[i] + b[j])

    print(min(dp[h:]))


if __name__ == '__main__':
    main()

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


a_max = max(a for a, b in ab)

dp = [0]*(h + a_max)

for i in range(h + a_max):
	if i > 0:
		dp[i] = min(dp[i - a] + b for a, b in ab)

print(min(dp[h:]))

Solution (Python):
n,m=map(int, input().split())
s=[list(map(int, input().split())) for i in range(m)]
x=max(a for a,b in s)
dp=[0]*(n+x)
for i in range(0,n+x):
  if i>0:
    dp[i]=min(dp[i-a]+b for a,b in s)
print(min(dp[n:]))

Solution (Python):
n,m=map(int, input().split())
s=[list(map(int, input().split())) for i in range(m)]
x=max(a for a,b in s)
dp=[0]*(n+x)
for i in range(0,n+x):
  if i>0:
    dp[i]=min(dp[i-a]+b for a,b in s)
print(min(dp[n:]))

Solution (Python):



from math import floor
import numpy

def main():
  h, n = map(int, input().strip().split())
  As, Bs = numpy.array([list(map(int, input().strip().split())) for _ in range(n)]).T

  dp = numpy.zeros(h+1)
  for i in range(1, len(dp)):
    dp[i] = numpy.min(dp[numpy.maximum(i - As, 0)] +  Bs)
  print(int(dp[-1]))



if __name__=='__main__':
  main()

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

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)

Ama = max(A)

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

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

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

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)

Ama = max(A)

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

for i in range(n):
    for j in range(A[i],h+Ama+1):
        dp[j]=min(dp[j],dp[j-A[i]]+B[i])

print(min(dp[h:]))

Solution (Python):
import numpy as np

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

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

A = np.array(A)
B = np.array(B)

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

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

print(solve())

Solution (Python):
import numpy as np

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

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

A = np.array(A)
B = np.array(B)

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

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

print(solve())

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 = [float("inf")] * (h + 10010)
dp[0] = 0

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

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

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)

Ama = max(A)

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

for i in range(n):
    for j in range(A[i], h+Ama+1):
        dp[j]=min(dp[j],dp[j-A[i]]+B[i])
print(min(dp[h:]))

Solution (Python):
import sys
import math
h, n = map(int, input().split())
INF = 10 ** 20
masics = []
for i in range(n):
  a, b = map(int, input().split())
  masics.append([a, b])
dp = [0] + [INF] * h

for masic in masics:
  for j in range(h):
    k = min(j+masic[0], h)
    dp[k] = min(dp[k], dp[j] + masic[1])

print(dp[h])

Solution (Python):
import sys


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    h, n = list(map(int, input().rstrip('\n').split()))
    ab = []
    ma = 0
    for i in range(n):
        a, b = list(map(int, input().rstrip('\n').split()))
        ab.append([a, b])
        ma = max(ma, a)
    ls = [10 ** 10] * (h + 1 + ma)
    ls[0] = 0
    for i in range(n):
        for j in range(h):
            ls[j+ab[i][0]] = min(ls[j] + ab[i][1], ls[j+ab[i][0]])
    print(min(ls[h:]))


if __name__ == '__main__':
    solve()

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

dp = [10**8] * (h+1)
dp[0] = 0

for i in range(1,h+1):
    for a,b in ab:
        if i >= a:
            
            atk = b + dp[i-a]
            if atk < dp[i]:
                dp[i] = atk
        elif b < dp[i]:
            
            dp[i] = b

print(dp[-1])

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

Solution (Python):
import numpy as np

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

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

A = np.array(A)
B = np.array(B)

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

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

print(solve())

Solution (Python):
import sys

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

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

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

ans = min(dp[H:])

print(ans)

Solution (Python):
n,m=map(int, input().split())
s=[list(map(int, input().split())) for i in range(m)]
x=max(a for a,b in s)
dp=[0]*(n+x)
for i in range(0,n+x):
  if i>0:
    dp[i]=min(dp[i-a]+b for a,b in s)
print(min(dp[n:]))

Solution (Python):
import numpy as np

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

Solution (Python):
n,m=map(int, input().split())
s=[list(map(int, input().split())) for i in range(m)]
x=max(a for a,b in s)
dp=[0]*(n+x)
for i in range(0,n+x):
  if i>0:
    dp[i]=min(dp[i-a]+b for a,b in s)
print(min(dp[n:]))

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.zeros(10001, dtype = int)

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

print(dp[h])

Solution (Python):
import sys

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

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

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

ans = min(dp[H:])

print(ans)

Solution (Python):



INF = float('inf')

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

for i in range(N):
    a_i, b_i = map(int, input().split())
    A.append(a_i)
    B.append(b_i)

dp = [[INF]*(H+1) for i in range(N+1)] 
dp[0][0] = 0 
for i in range(0,N):
    for j in range(0,H+1):
        a, b = j+A[i], H
        min_h = a
        if a>b:
            min_h = b
        a, b = dp[i+1][j], dp[i][j]
        if a>b:
            dp[i+1][j] = b
        a, b = dp[i+1][min_h], dp[i+1][j]+B[i]
        if a>b:
            dp[i+1][min_h] = b

print(dp[N][H])

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

magic = [list(map(int, input().split())) for _ in range(N)]
inf = float('inf')
dp = [inf] * (H + 1)
dp[0] = 0
for i in range(H):
    if dp[i] == inf:
        continue
    currCost = dp[i]
    for dmg, cost in magic:
        totalDmg = i + dmg
        if totalDmg > H:
            totalDmg = H
        totalCost = currCost + cost
        if totalCost < dp[totalDmg]:
            dp[totalDmg] = totalCost
print(dp[H])

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

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

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

inf = 10**8
dp = [[inf for i in range(h+10001)] for j in range(n+1)]
dp[0][0] = 0
a = []
b = []
for i in range(n):
    A, B = map(int, input().split())
    a.append(A)
    b.append(B)

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

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

Solution (Python):
import sys

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

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

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

ans = min(dp[H:])

print(ans)

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

H,N = map(int, input().split())
table = []
dp = [10**9]*(H+1)
dp[0] = 0

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

for i in range(1,H+1):

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

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

a=[]
b=[]
INF=10**9
dp=[INF for i in range(h+10**4)]

for i in range(n):
  p,q=map(int,input().split())
  a.append(p)
  b.append(q)

dp[0]=0
for i in range(h):
  if dp[i]==INF:
    continue
  for j in range(n):
    if dp[i+a[j]]>=dp[i]+b[j]:
      dp[i+a[j]]=dp[i]+b[j]
print(min(dp[h:]))