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())
magics = sorted(list(map(int, input().split())) for _ in range(n))
max_cost = max(magic[1] for magic in magics)

dp = [float('inf')] * (h+max_cost)
dp[0] = 0
for i in range(h+max_cost):
    for at, cost in magics:
        if at <= i:
            dp[i] = min(dp[i], dp[i-at] + cost)
        else:
            break
print(min(dp[h:]))

Solution (Python):

import math

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

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


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

for h in range(H):
  for d, m in mahou:
    new_hp = min(h + d, H)
    dp[new_hp] = min(dp[new_hp], dp[h] + m)
print(int(dp[-1]))

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

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

print(dp[-1])

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

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

print(dp[-1])

Solution (Python):
def main():
    H, N = map(int, input().split())
    A = [0] * N
    B = [0] * N
    for i in range(N):
        A[i], B[i] = map(int, input().split())

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

    print(dp[H])

if __name__ == "__main__":
    main()

Solution (Python):
def main():
    H, N = map(int, input().split())
    A = [0] * N
    B = [0] * N
    for i in range(N):
        A[i], B[i] = map(int, input().split())

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

    print(dp[H])
if __name__ == "__main__":
    main()

Solution (Python):

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

max_a = max(AB[i][0] for i in range(N))
DP = [10**18 for i in range(H + max_a + 1)]
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 = []
for i in range(N):
    a, b = map(int, input().split())
    AB.append([a,b])
AB.sort()

DP = [float('inf') for i in range(2*10**4 + 1)]
DP[0] = 0
for i in range(H):
    for ab in AB:
        DP[i+ab[0]] = min(DP[i+ab[0]], DP[i] + ab[1])

print(min(DP[H:]))

Solution (Python):
H, N = map(int, input().split())
magics = []
for n in range(N):
    A, B = map(int, input().split())
    magics.append([A, B])

maxa = max(A for A, _ in magics)  

point = [0]*(H+maxa)
for i in range(1, H+maxa):
    point[i] = min(point[i-a]+b for a,b in magics)
print(min(point[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)]

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

Solution (Python):
from operator import itemgetter
h,n=map(int,input().split())
ab=[list(map(int,input().split())) for i in range(n)]
infi=10**9
dp=[infi]*2*10**4
dp[0]=0
for a,b in ab:
  for i in range(h):
    if dp[i]!=infi:
      dp[i+a]=min(dp[i+a],dp[i]+b)
print(min(dp[h:]))

Solution (Python):
import sys
sys.setrecursionlimit(100000000)

INF = 10**10
def solve(h, n, a, b):
    ab = sorted(zip(a, b), key=lambda _:(_[0]/_[1], -_[0]), reverse=True)
    dp = [-1] * h
    def f(h):
        best = INF
        for x, y in ab:
            if h-x <= 0:
                score = y
            else:
                if dp[h-x] == -1:
                    dp[h-x] = f(h-x)
                score = y + dp[h-x]
            if score < best:
                best = score
            else:
                break
        return best
    return f(h)

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())
print(solve(h, n, a, b))

Solution (Python):
import sys, math

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

def main():
    H, N = map(int,input().split())
    M = [list(map(int,input().split())) for k in range(N)]

    dp = [10**9 for k in range(10**4+1)]
    dp[0] = 0
    for e in M:
        A, B = e[0], e[1]
        for k in range(A+1):
            dp[k] = min(dp[k],B)
        for k in range(A+1,H+1):
            dp[k] = min(dp[k],dp[k-A]+B)

    print(dp[H])

if __name__ == '__main__':
    main()

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

h,n=map(int,input().split())
a=[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):
    for j in range(1,h+1):
        if j<a[i][0]:
            dp[j]=min(dp[j],dp[0]+a[i][1])
        else:
            dp[j]=min(dp[j-a[i][0]]+a[i][1],dp[j])
print(dp[-1])

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

ans = [-1] * (h + 1)
ans[0] = 0

for i in range(h):
    if (ans[i] >= 0):
        for j in range(n):
            next = min(h, i + a[j])
            if ans[next] < 0:
                ans[next] = ans[i] + b[j]
            else:
                ans[next] = min(ans[next], ans[i] + b[j])

print(ans[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)

X = []

for i in range(H):
	Y = []
	for j in range(N):
		if i+1 <= A[j]:
			Y.append(B[j])
		else:
			Y.append(X[i-A[j]] + B[j])
	
	X.append(min(Y))

print(X[H-1])

Solution (Python):
H,N=list(map(int,input().split()))
M=[list(map(int,input().split())) for i in range(N)]
A=[M[i][0] for i in range(len(M))] 
B=[M[i][1] for i in range(len(M))] 


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

for h in range(1,H+1):
    dp[h]=min(dp[h - a] + b for a, b in zip(A,B))  

print(dp[H])

Solution (Python):
import sys
Mx = 999999999

H, N = map(int,sys.stdin.readline().split())
L = [list(map(int,sys.stdin.readline().split())) for i in range(N)]

D = [Mx] * 40000

D[0] = 0

for i in range(H+1):
    for spell in L:
        if D[i] + spell[1] < D[i+spell[0]]:
            D[i+spell[0]] = D[i] + spell[1]

sys.stdout.write(str(min(D[H:])))

Solution (Python):





import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols

    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])

    return ret


H, N = read_ints()
A, B = read_col(N, 2)
minb = min(B)
maxa = max(A)
INF = 10**10 + 1

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

for i in range(1, H + 1 + maxa):
    for a, b in zip(A, B):
        if i - a < 0:
            continue
        dp[i] = min(dp[i], dp[i - a] + b)





print(min(dp[H:]))

Solution (Python):
h, n = map(int, input().split())
c = [0]*n
m = [0]*n

mc = 0
for i in range(n):
    c[i], m[i] = map(int, input().split())
    if mc < c[i]:
        mc = c[i]
    
dp = [10**10]*(h+mc)
dp[0] = 0

for i in range(1, h + mc):
    dp[i] = min(dp[i-a] + b for a, b in zip(c, m))
        
print(min(dp[h:]))

Solution (Python):
def main():
    h, n = map(int, input().split())
    magic_list = []

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

    ans = solve(h, magic_list)
    print(ans)


def solve(h, magic_list):
    
    max_attack = max(magic_list)[0]
    dp = [0] * (h + max_attack)

    
    for hp in range(1, h + 1):
        dp[hp] = min(dp[hp - attack] + mp for attack, mp in magic_list)

    return dp[h]


main()

Solution (Python):
def main():
    h, n = map(int, input().split())
    magic_list = []

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

    ans = solve(h, magic_list)
    print(ans)


def solve(h, magic_list):
    
    max_attack = max(magic_list)[0]
    dp = [0] * (h + max_attack)

    
    for hp in range(1, h + 1):
        dp[hp] = min(dp[hp - attack] + mp for attack, mp in magic_list)

    return dp[h]


main()

Solution (Python):
def main():
    h, n = map(int, input().split())
    magic_list = []

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

    ans = solve(h, magic_list)
    print(ans)


def solve(h, magic_list):
    
    inf = 1 << 40
    max_attack = max(magic_list)[0]
    dp = [inf] * (h + max_attack)
    dp[0] = 0

    
    for hp in range(1, h + max_attack):
        for attack, mp in magic_list:
            if hp >= attack and dp[hp - attack] < inf:
                dp[hp] = min(dp[hp], dp[hp - attack] + mp)

    return min(dp[h:])


main()

Solution (Python):
h, n = map(int, input().split())
magic_cost = []
for _ in range(n):
    magic, cost = map(int, input().split())
    magic_cost.append((magic, cost))

dp = [float('infinity')] * h

for i in range(h):
    for j in range(n):
        magic, cost = magic_cost[j]
        if i >= magic:
            dp[i] = min(dp[i], dp[i - magic] + cost)
        else:
            dp[i] = min(dp[i], cost)

print(dp[-1])

Solution (Python):
h,n = map(int, input().split())
magic = []
INF = 10**8
dp = [[INF for j in range(h+1)] for i in range(n+1)] 
 
for i in range(n):
    a,b = map(int, input().split())
    magic.append([a, b])
 
for i in range(n):
    for j in range(h):
        if j+1 > magic[i][0]:
            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])
        else:
            dp[i+1][j+1] = min(dp[i][j+1], magic[i][1])
            
print(dp[n][h])

Solution (Python):
h,n = map(int, input().split())
magic = []
INF = 10**8
 
for i in range(n):
    a,b = map(int, input().split())
    magic.append([a, b])
 
dp = [[INF for j in range(h+1)] for i in range(n+1)] 
 
for i in range(n):
    for j in range(h):
        if j+1 > magic[i][0]:
            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])
        else:
            dp[i+1][j+1] = min(dp[i][j+1], magic[i][1])
            
print(dp[n][h])

Solution (Python):
import sys
input = sys.stdin.readline
H,N = [int(i) for i in input().split()]
A = [0] * N
B = [0] * N
for i in range(N) :
    a,b = [int(i) for i in input().split()]
    A[i] = a
    B[i] = b
dp = [[(10**9+7)] * (H+1) for _ in range(N)]
for j in range(H+1):
    if j <= A[0]:
        dp[0][j] = B[0]
    if j > A[0]:
        dp[0][j] = dp[0][j-A[0]] + B[0]
for i in range(1,N):
    for j in range(H+1):
        if j == 0:
            dp[i][j] = min(dp[i-1][0],B[i])
        if j <= A[i]:
            dp[i][j] = min(dp[i-1][j],B[i])
        if j > A[i]:
            dp[i][j] = min(dp[i-1][j],dp[i][j-A[i]]+B[i])
print(dp[N-1][H])

Solution (Python):
H, N = map(int, input().split())
ls = []
x = 0
for i in range(N):
  a, b = map(int, input().split())
  ls += [(a,b)]
  if a>x:
    x = a

L = x+H+1
dp = [10**9]*L
dp[0] = 0
for i in range(L):
  for j in range(N):
    a, b = ls[j]
    if i>=a:
      dp[i] = min(dp[i], dp[i-a]+b)

ans = min(dp[H:])

print(ans)

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

max_ab = max(AB)
dp = [10**10]*(H+max_ab[0])
dp[0] = 0

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

print(min(dp[H:]))

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

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

Solution (Python):
H, N = map(int, input().split())
x = [list(map(int, input().split())) for n in range(N)]
x = [[tmp[i] for tmp in x] for i in range(len(x[0]))]
A = x[0]
B = x[1]

def ibis(H, A, B):
    dp = [max(B) * H] * (H + 1)
    dp[0] = 0
    for h in range(H):
        for n in range(N):
            hp = min(h + A[n], H)
            dp[hp] = min(dp[hp], dp[h] + B[n])
    return dp[H]

print(ibis(H, A, B))

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())
a, b = [0]*N, [0]*N
for i in range(N):
    a[i], b[i] = map(int, input().split())
dp = [[float('inf')] * (H+1) for _ in range(N+1)]
for i in range(N+1):
    dp[i][0] = 0
for i in range(N):
    for j in range(H+1):
        if j - a[i] <= 0:
            dp[i+1][j] = min(dp[i][j],b[i])
        else:
            dp[i+1][j] = min(dp[i][j],dp[i+1][j-a[i]]+b[i])
print(dp[N][H])

Solution (Python):
def main():
  h, n = map(int,input().split())
  magics = []
  for i in range (n):
    a, b = map(int,input().split())
    magics.append([a,b])
  
  dp = [0] * (h + max(a for a, b in magics))
  for i in range(1, h + 1):
    dp[i] = min(dp[i - a] + b for a, b in magics)
  print(dp[h])  

if __name__ == '__main__':
  main()

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

c = [min(b)] + [h*max(b)]*(h-1)

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

Solution (Python):
h, n = list(map(int, input().split()))
ab = []
for i in range(n):
    a, b = list(map(int, input().split()))
    ab.append((a, b))
ab.sort(key=lambda ab: (ab[0]/ab[1], -ab[0]), reverse=True)

import sys
sys.setrecursionlimit(100000000)

mem = [-1 for i in range(h)]
def solve(h):
    best = float('inf')
    for a,b in ab:
        if h - a <= 0:
            val = b
        else:
            if mem[h - a] != -1:
                val = b + mem[h - a]
            else:
                mem[h - a] = solve(h - a)
                val = b + mem[h-a]
        if val < best:
            best = val
        else:
            break
    return best

print(solve(h))

Solution (Python):
H,N = map(int,input().split())
Magic =[]
A =[]
E =[]
for i in range(N):
    a,b = map(int,input().split())
    Magic.append((a,b))
    A.append(a)
    E.append(a/b)
MAX_A = H+max(A)
E_MIN = min(E)
WORST = int(MAX_A/E_MIN) +2
DP = [[WORST] * (MAX_A+1) for i in range(N)]
for i in range(N):
    if i == 0:
        for j in range(1,MAX_A//Magic[0][0]+1):
            DP[0][j*Magic[0][0]] = Magic[0][1]*j
    else:
        for j in range(Magic[i][0]-1):
            DP[i][j] = DP[i-1][j]
        DP[i][Magic[i][0]] = min(DP[i-1][Magic[i][0]],Magic[i][1])
        for j in range(Magic[i][0]+1,(MAX_A+1)):
            DP[i][j]=min(DP[i-1][j],DP[i-1][j-Magic[i][0]]+Magic[i][1],DP[i][j-Magic[i][0]]+Magic[i][1])
print(min(DP[N-1][H:MAX_A]))

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

dp = [10**18] * (H+max_A)
dp[0] = 0


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

Solution (Python):
H,N = map(int,input().split())
Magic =[]
A =[]
E =[]
for i in range(N):
    a,b = map(int,input().split())
    Magic.append((a,b))
    A.append(a)
    E.append(a/b)
MAX_A = H+max(A)
E_MIN = min(E)
WORST = int(MAX_A/E_MIN) +2



DP = [[WORST] * (MAX_A+1) for i in range(N)]
for i in range(N):
    if i == 0:
        for j in range(1,MAX_A//Magic[0][0]+1):
            DP[0][j*Magic[0][0]] = Magic[0][1]*j
    else:
        for j in range(Magic[i][0]-1):
            DP[i][j] = DP[i-1][j]
        DP[i][Magic[i][0]] = min(DP[i-1][Magic[i][0]],Magic[i][1])
        for j in range(Magic[i][0]+1,(MAX_A+1)):
            DP[i][j]=min(DP[i-1][j],DP[i-1][j-Magic[i][0]]+Magic[i][1],DP[i][j-Magic[i][0]]+Magic[i][1])
            if j % Magic[i][0] == 0:
                DP[i][j]=min(DP[i][j],((j//Magic[i][0]) * Magic[i][1]))
print(min(DP[N-1][H:MAX_A]))

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

cost = [float('inf')] * (H+1)
cost[0] = 0
magics = [tuple(map(int, input().split())) for _ in range(N)]
for hp in range(0, H+1):
    now_cost = cost[hp]
    for a, b in magics:
        reduced_hp = a+hp
        if a + hp > H:
            reduced_hp = H
        cost[reduced_hp] = min(cost[reduced_hp], now_cost+b)
print(cost[H])

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

dp=[10**10]*(H+1)
dp[0]=0
for n in range(N):
  a,b=map(int, input().split())
  A.append(a)
  B.append(b)
    
for h in range(1,H+1):
  for n in range(N):
    if h-A[n]>=0:
      dp[h]=min(dp[h],dp[h-A[n]]+B[n])
    else:
      dp[h]=min(dp[h],B[n])
print(dp[H])

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

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

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

for i in range(1,h+10**4+1):
    for j in range(n): 
        if i>=lis[j][0]:
            dp[i]=min(dp[i],dp[i-lis[j][0]]+lis[j][1])
print(min(dp[h:]))

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

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

for i in range(1,h+10**4+1):
    for j in range(n): 
        if i>=lis[j][0]:
            dp[i]=min(dp[i],dp[i-lis[j][0]]+lis[j][1])


print(min(dp[h:]))

Solution (Python):
H, N = map(int, input().split())
da, cost = [0] * N, [0] * N
for i in range(N):
    da[i],cost[i]=map(int, input().split())

max_da=max(da) 
dp = [float("inf") for i in range(H+max_da)]
dp[0]=0

for i in range(H+max_da):
    for j in range(N):
        if i-da[j]>=0:
            dp[i]=min(dp[i],dp[i-da[j]]+cost[j])

print(min(dp[H:]))

Solution (Python):
H, N = map(int, input().split())
AB = []
ma = -1
for _ in range(N):
    a, b = map(int, input().split())
    ma = max(ma, a)
    AB.append([a, b])


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

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



ans = inf
for i in range(H, H + ma + 1):
    ans = min(dp[i], ans)

print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
h, n = [int(x) for x in input().strip().split()]
a = [0] * n
b = [0] * n
for i in range(n):
    a[i], b[i] = [int(x) for x in input().strip().split()]

dp = [float('inf')] * (h + 1)
dp[0] = 0
for i in range(1, h+1):
    for aa, bb in zip(a, b):
        dp[i] = min(dp[i], dp[max(0, i-aa)]+bb)
print(dp[h])

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

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

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

Solution (Python):
import math
import sys
input = sys.stdin.readline
def main():
	H,N = map(int,input().split())
	A,B = [],[]
	ap = A.append
	bp = B.append
	for _ in range(N):
		a,b = map(int,input().split())
		ap(a)
		bp(b)
	
	dp = [[0 for _ in range(H+1)] for _ in range(N)]
	
	for i in range(1,H+1):
		dp[0][i] = math.ceil(i/A[0])*B[0]

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

	print(dp[N-1][H])
if __name__ == '__main__':
	main()

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

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

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


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

for i in range(h):
    for d, c in magic:
        next_index = min(i+d, h)
        dp[next_index] = min(dp[next_index], dp[i]+c)
        

print(dp[-1])

Solution (Python):
import sys

input = sys.stdin.buffer.readline


def main():
	H,N=map(int,input().split())
	
	INF = 1001001001
	
	mAB=[tuple(map(int,input().split())) for _ in [0,]*N]
	
	vN = [INF,]*(H+2)
	vN[0] = 0
	
	
	
	
	for h in range(H+2):
		
		for a,b in mAB:
			j = min(h+a,H+1)
			vN[j] = min(vN[h]+b, vN[j])
		
		
	
	res = min(vN[-2:])
	print(res)

main()

Solution (Python):
from functools import lru_cache
import sys

sys.setrecursionlimit(1000000)

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

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

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


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


print(solve(H))

Solution (Python):
def main():
    H, N = [int(x) for x in input().split()]
    magic = [list(map(int, input().split())) for _ in range(N)]
    
    max_a = max(a for a, _ in magic)
    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 magic)

    ans = min(dp[H:H+max_a])
    print(ans)


if __name__ == '__main__':
    main()

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

Solution (Python):
h, n = map(int, input().split())
p = [0] * n
c = [0] * n

inf = 1e9 + 1

for i in range(n):
    pp, cc = map(int, input().split())
    p[i] = pp
    c[i] = cc
    
dp = [inf] * (h + max(p))
dp[0] = 0

for i in range(n):
    for j in range(h):
        dp[j + p[i]] = min(dp[j + p[i]], dp[j] + c[i])
    
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 = [0]*(H+max_a)
for i in range(1,H+1):
  dp[i] = min(dp[i-a]+b for a,b in ab)
print(dp[H])

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

print(dp[H])

Solution (Python):
inf = 10**9
H, N = map(int, input().split())
AB = []
for n in range(N):
    a, b = map(int, input().split())
    AB.append((a, b))
AB.sort(reverse=True, key=lambda x: x[0])
dp = [inf] * (H + 10 ** 4)
dp[0] = 0
for a, b in AB:
    for h in range(H):
        if dp[h] != inf:
            tmp = dp[h] + b
            if tmp < dp[h + a]:
                dp[h + a] = tmp
print(min(dp[H:]))

Solution (Python):
h,n = map(int,input().split())
inf = 10**10
magic = [list(map(int,input().split())) for i in range(n)]
max_a = max(a for a,b in magic)
dp = [inf for i 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 magic)
print(min(dp[h:]))

Solution (Python):
def read_values():
    return map(int, input().split())


def read_list():
    return list(read_values())


def main():
    H, N = read_values()
    M = [read_list() for _ in range(N)]

    dp = [10 ** 12] * (H + max(M, key=lambda m: m[0])[0] + 10)
    dp[0] = 0
    for h in range(H + 1):
        for a, b in M:
            dp[h + a] = min(dp[h + a], dp[h] + b)
    
    print(min(dp[H:]))


if __name__ == "__main__":
    main()

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

Solution (Python):
import sys
def input():
  return sys.stdin.readline()[:-1]
h, n = map(int, input().split())
a=[0]*n
b=[0]*n
for i in range(n):
  a[i], b[i] = map(int, input().split())

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

Solution (Python):
import sys
def input():
  return sys.stdin.readline()[:-1]
h, n = map(int, input().split())
a=[0]*n
b=[0]*n
for i in range(n):
  a[i], b[i] = map(int, input().split())

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

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

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

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

Solution (Python):
import 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.int)
for c in range(1, h+1):
  dp[c] = np.min(dp[np.maximum(0, c-a)] + b)
print(dp[-1])

Solution (Python):
import numpy as np
h, n = map(int, input().split())    
ab = np.array([tuple(map(int, input().split())) for _ in range(n)])
dp = np.zeros(h + 1, dtype="int")
for i in range(1, h+1):
    dp[i] = np.min(dp[np.maximum(i - ab[:, 0], 0)] + ab[:, 1])
print(dp[-1])

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

inf=10**9
dp=[[0]+[inf]*hp for i in range(n+1)]
for i in range(n):
  damage=magics[i][0]
  cost=magics[i][1]
  for j in range(hp+1):
    if j<damage:
      dp[i+1][j]=min(dp[i][j],cost)
    else:
      dp[i+1][j]=min(dp[i][j],(dp[i+1][j-damage]+cost))
print(dp[n][hp])

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


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

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

DP = []
for _ in range(n + 1):
    DP.append([0] + [float("inf")] * h)

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

print(DP[n][h])

Solution (Python):
h, n = map(int, input().split())
a, b = [0]*n, [0]*n

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

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

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

print(dp[-1])

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

Solution (Python):
from subprocess import*
call(('pypy3','-c',"""
h,n=[int(j) for j in input().split()]
ab=[[int(j) for j in input().split()] for i in range(n)]
dp=[10**18]*(h+1)
dp[0]=0
ans=10**18
for a,b in ab:
    for i in range(h+1):
        if dp[i]!=10**18:
            if i+a<h:
                if dp[i]+b<dp[i+a]:
                    dp[i+a]=dp[i]+b
            else:
                if dp[i]+b<ans:
                    ans=dp[i]+b
 
print(ans)

"""))

Solution (Python):
def run():
  H, N = map(int, input().split())
  ab = [list(map(int, input().split())) for n in range(N)]
  dp = [float('inf')]*(H+1)
  for h in range(H+1):
    for n in range(N):
      a, b = ab[n]
      if h <= a:
        dp[h] = min(dp[h], b)
      else:
        dp[h] = min(dp[h], dp[h-a]+b)
  print(dp[-1])
    
if __name__ == '__main__':
    run()

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

maxi=max(A)
DP=[0]*(H+maxi)
DP[0]=0

for i in range(1,H+maxi):
  mini=float("inf")
  for j in range(N):
    if i-A[j]>=0:
      mini=min(mini, DP[i-A[j]]+B[j])
  DP[i]=mini
  
mini2=float("inf")
for k in range(H,H+maxi):
  mini2=min(mini2,DP[k])

print(mini2)