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())
abl = [tuple(map(int, input().split())) for _ in range(n)]

dp = [10**18]*(h+1)
dp[0] = 0
for i in range(h):
    for a,b in abl:
        next_h = min(h,i+a)
        dp[next_h] = min(dp[next_h], dp[i]+b)

print(dp[-1])

Solution (Python):
H, N = map(int,input().split())
M = [list(map(int,input().split())) for k in range(N)]
dp = [10**10]*(10**5)
dp[0] = 0
for e in M:
    for k in range(e[0],10**5):
        dp[k] = min(dp[k],dp[k-e[0]]+e[1])
print(min(dp[H:]))

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


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

for i in range(H+10**4+1):
    for j in range(N):
        if l[j][0] <= i:
            dp[i] = min(dp[i],dp[i-l[j][0]]+l[j][1])

ans = dp[H]
for i in range(1,10**4+1):
    ans = min(ans,dp[H+i])

print(ans)

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

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

dp = [[10**8+1]*(H) for _ in range(N+1)] 

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


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

Solution (Python):
h,n=map(int,input().split())
ma=[]
for _ in range(n):
  a=list(map(int,input().split()))
  ma.append(a)
  
inf=float('inf')
dp=[inf for _ in range(h+1) ]

dp[h]=0

for i in range(1,h+1):
  j=h+1-i
  for x in ma:
    p=x[0]
    q=x[1]
    if j-p>=1:
      dp[j-p]=min(dp[j-p],dp[j]+q)
    else:
      dp[0]=min(dp[0],dp[j]+q)
      
print(dp[0])

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)





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

Solution (Python):



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


dp = [0] * 20001

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

Solution (Python):
H, N = map(int, input().split())
M = [tuple(map(int, input().split())) for i in range(N)]
Mmax = max(M, key=lambda x: x[0])[0]
dp = [0 for i in range(H + Mmax + 1)]

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

print(min(dp[H:]))

Solution (Python):
h,n = map(int, input().split())
magics = [tuple(map(int, input().split())) for _ in range(n)]
max_a = max(magics, key=lambda x: x[0])[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 magics)
print(min(dp[h:]))

Solution (Python):
h,n = map(int, input().split())
magics = [tuple(map(int, input().split())) for _ in range(n)]
max_a = sorted(magics, key=lambda x: x[0], reverse=True)[0][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 magics)
print(min(dp[h:]))

Solution (Python):
import sys
sys.setrecursionlimit(10**5)

h,n=map(int,input().split())
magic=[]
for i in range(n):
  magic.append(tuple(map(int,input().split())))

memo={}
def d(hp):
  if hp<=0:
    return 0
  if hp in memo:
    return memo[hp]
  mn=10**10
  for i in magic:
    mn=min(mn,d(hp-i[0])+i[1])
  memo[hp]=mn
  return mn

for i in range(1,h-1):
  d(i)
print(d(h))

Solution (Python):
h,n=map(int,input().split())
c=[list(map(int,input().split()))for _ in range(n)]
d=[0]+[0]*20001
for i in range(h):
    d[i]=min(d[i-a]+b for a,b in c)
print(d[h-1])

Solution (Python):
h,n=map(int,input().split())
c=[list(map(int,input().split()))for _ in range(n)]
d=[0]*20002
for i in range(h):
    d[i]=min(d[i-a]+b for a,b in c)
print(d[h-1])

Solution (Python):
h,n=map(int,input().split())
c=[list(map(int,input().split()))for _ in range(n)]
d=[0]*20002
for i in range(h):d[i]=min(d[i-a]+b for a,b in c)
print(d[h-1])

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

ans=[10**9]*(H+1)
ans[0]=0
i=0
while i<=H:
    for a,b in ab:
        if a+i>H:
            a=H-i
        if ans[i+a]>ans[i]+b:
            ans[i+a]=ans[i]+b
    i+=1

print(ans[H])

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

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

dp[0] = 0

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

res = dp[H]

print(res)

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

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

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

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


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

Solution (Python):
import sys
input = sys.stdin.buffer.readline
H, N = map(int, input().split())
A = [tuple(map(int, line.split())) for line in sys.stdin.buffer.readlines()]
INF = 1 << 30
dp = [INF]*(H+1)
dp[H] = 0
for i in range(N):
    a, b = A[i]
    for h in range(H, -1, -1):
        x = h-a if h-a > 0 else 0
        if dp[x] > dp[h]+b:
            dp[x] = dp[h]+b
print(dp[0])

Solution (Python):
H,N=map(int,input().split())
L=[tuple(map(int,input().split())) for i in range(N)]
dp=[[-1]*(H+1) for i in range(N+1)]
for d in dp:
    d[0]=0
dp[0]=[10**9]*(H+1)
i=1
for a,b in L:
    for j in range(H+1):
        if j<a:
            dp[i][j]=min(dp[i-1][j],b)
        else:
            dp[i][j]=min(dp[i-1][j],dp[i][j-a]+b)
    i+=1
print(dp[N][H-1])

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

DP = [float("inf") for _ in range(h+1)]
DP[0] = 0

for i in range(h):
    for damage, cost in AB:
        next_index = min(i+damage, h)
        DP[next_index] = min(DP[next_index], DP[i]+cost)

print(DP[-1])

Solution (Python):
H, N = map(int, input().split())
AB=[[int(ab) for ab in input().split()] for n in range(N)]
dp=[0]*(20001)
for h in range(1, H+1):
  dp[h]=min(dp[h-a] + b for (a, b) in AB)
print(dp[H])

Solution (Python):
def num():
    from sys import stdin
    h, n = map(int, input().split())
    magic = [list(map(int, stdin.readline().split())) for _ in range(n)]
    INF = float('inf')
    ans = [INF]*(h+1)
    ans[-1] = 0

    for i in range(h, 0, -1):
        if ans[i] != INF:
            for j, k in magic:
                if i-j < 0:
                    num = ans[i]+k
                    if ans[0] > num:
                        ans[0] = num
                else:
                    num = ans[i]+k
                    if ans[i-j] > num:
                        ans[i-j] = num
    return ans[0]
print(num())

Solution (Python):
import sys
input = sys.stdin.readline
H,N = map(int,input().split())
spells = [list(map(int,input().split())) for i in range(N)]
INF = 10**10
dp = [INF]*(H+1)
dp[0] = 0
for use in spells:
    damage = use[0]
    mp = use[1]
    for i in range(1,H+1):
        dp[i] = min(dp[max(0,i-damage)] + mp, dp[i])
print(dp[-1])

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

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

inf = float("inf")

dp = [[inf]*(h+2) 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][min(j+a[i],h)],dp[i+1][j]+b[i])

print(dp[n][h])

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

H, N = map(int, input().split())
AB = [tuple(map(int, input().split())) for _ in range(N)]
dp = [10**18]*(H+1)
dp[0] = 0

for i in range(H):
    for A, B in AB:
        j = min(H, i+A)
        dp[j] = min(dp[j], dp[i]+B)

print(dp[H])

Solution (Python):
import sys, math

input = sys.stdin.readline
H, N = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(N)]
max_a = max([a for a, b in ab])
dp = [math.inf] * (H+max_a+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):

INF = 100000000
H,N = map(int,input().split())
ab = [list(map(int,input().split())) for _ in range(N)]
c = [INF]*H+[0]
for i in range(N):
    A,B = ab[i]
    for h in range(H,0,-1):
        k = max(0,h-A)
        c[k] = min(c[k], c[h]+B)
print(c[0])

Solution (Python):
import numpy as np
import numba
from numba import njit, b1, i4, i8, f8

@njit((i8,i8,i8[:],i8[:]), cache=True)
def main(H,N,A,B):
  INF = 1<<30
  dp = np.full(H+1,INF,np.int64)
  dp[0] = 0
  for i in range(N):
    for h in range(A[i],H):
      dp[h] = min(dp[h],dp[h-A[i]]+B[i])
    dp[H] = min(dp[H],min(dp[H-A[i]:H]+B[i]))
  ans = dp[-1]
  return ans

H, N = map(int, input().split())
A = np.zeros(N,np.int64)
B = np.zeros(N,np.int64)
for i in range(N):
  A[i],B[i] = map(int, input().split())
print(main(H,N,A,B))

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

Solution (Python):

f=lambda:map(int,input().split())
H,N=f()

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

for i in range(N+1):
    if i!=0:
        a,b=f()
    else:
        a,b=0,0
    for j in range(H+1):
        if i==0:
            if j==0:
                dp[i][j]=0
            else:
                dp[i][j]=INF
        else:
            dp[i][j]=min(dp[i-1][j],dp[i][max(j-a,0)]+b)

print(dp[N][H])

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

magics = [None]


class Magic:
    def __init__(self, attack, cost):
        self.attack = attack
        self.cost = cost


maxA = 0
for i in range(n):
    attack, cost = [int(i) for i in input().split()]
    maxA = max(maxA, attack)
    magics.append(Magic(attack, cost))

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

for i in range(n + 1):
    for j in range(h + maxA):
        if j == 0:
            dp[i][j] = 0
        elif i == 0:
            continue
        elif j - magics[i].attack >= 0:
            dp[i][j] = min(dp[i - 1][j], dp[i][j - magics[i].attack] + magics[i].cost)
        else:
            dp[i][j] = dp[i - 1][j]

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

Solution (Python):
h, n = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(n)]
dp = [0] + [10000000000] * h
ret = 10000000000
for i in range(h):
    for j in range(n):
        a, b = ab[j]
        if i + a >= h:
            ret = min(ret, dp[i] + b)
        else:
            dp[i + a] = min(dp[i + a], dp[i] + b)
print(ret)

Solution (Python):
H, N = list(map(int, input().split()))
dp = [[float('inf')] * (H + 1)]
dp[0][0] = 0
magic = []
for i in range(N):
  magic.append(list(map(int, input().split())))
  
for i in range(H+1):
  next = dp[i]
  if dp[i][i] != float('inf'):
    for j in magic:
      next[min(H, i + j[0])] = min(dp[i-1][i] + j[1], dp[i][min(H, i + j[0])])
  dp.append(next)

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

Solution (Python):
import math
H, N = map(int, input().split())
dp = [[0 for _ in range(H + 1)] for _ in range(N)]
A, B = map(int, input().split())
for i in range(H + 1):
    cnt = math.ceil(i / A)
    dp[0][i] = B * cnt

for i in range(1, N):
    A, B = map(int, input().split())
    for j in range(H + 1):
        dp[i][j] = min(dp[i - 1][j], dp[i][max(j - A, 0)] + B)

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

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


dp=[[float("INF") for i in range(h+1)] for j in range(n+1)]

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

print(dp[n][h])

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

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

print(dp[h])

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

for i in range(1, h + 1):
    ref = 10**10
    for a, b in l:
        temp = dp[i - a] + b
        ref = min(ref, temp)
    dp[i] = ref

print(dp[h])

Solution (Python):
H,N = map(int,input().split())
inf = 1000000000
dp = [inf for _ in range(20001)]
magics = []
dp[0] = 0
for i in range(N):
    magic = list(map(int,input().split()))
    magics.append(magic)
for j in range(10001):
    for k in magics:
        dp[j+k[0]] = min(dp[j]+k[1],dp[j+k[0]])
ans = dp[H:]
print(min(ans))

Solution (Python):
H, N = list(map(int, input().split()))
A = [[0]*2 for _ in range(N)]
for _ in range(N):
    A[_][0], A[_][1] = list(map(int, input().split()))



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

for i in range(H):
    if dp[i] == INF:
        continue
    for j in range(N):
        a = A[j][0]
        b = A[j][1]
        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())
a=[]
b=[]
for i in range(n):
  aa,bb=map(int,input().split())
  a.append(aa)
  b.append(bb)
inf=10**10
f=h+max(a)+1
dp=[f*[inf]for _ in range(n+1)]
dp[0][0]=0
for i in range(1,n+1):
  dp[i]=dp[i-1]
  for j in range(f):
    if j+a[i-1]<f:
      dp[i][j+a[i-1]]=min(dp[i][j+a[i-1]],dp[i][j]+b[i-1])
  for j in range(f-1,0,-1):
    dp[i][j-1]=min(dp[i][j-1],dp[i][j])
print(dp[-1][h])

Solution (Python):
from sys import stdin
import numpy as np
from numba import njit

H,N = map(int, input().split())
M = [list(map(int, stdin.readline().split())) for i in [0]*N]
M = np.array(M)

@njit
def main(h,n,m):
    dp = [10**8+1]*(10**4+1)
    dp = np.array(dp)
    dp[0] = 0

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

    print(dp[h])

if __name__=="__main__":
    main(H,N,M)

Solution (Python):
import math

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

dp = [0]*(H+1)

dp[0] = 0

for i in range(1,H+1):
    dp_min = math.inf
    for j in range(N):
        dp_min = min(dp_min, dp[max(0,i-A[j])] + B[j])
    dp[i] = dp_min

print(dp[H])

Solution (Python):
H, N = map(int, input().split())
l = []
for i in range(N):
  l.append(list(map(int, input().split())))
  
dp = [0] * 20000
for i in range(1, 20001):
  dp[i] = min(dp[i-a]+b for a, b in l)
  if i == H:
    break
print(dp[H])

Solution (Python):


def read_input():
    h, n = map(int, input().split())
    magic = {}
    for i in range(n):
        a, b = map(int, input().split())
        magic[i] = (a, b)

    return h, n, magic


def submit():
    h, n, magic = read_input()

    dp = [float('inf') for _ in range(h + 1)]
    dp[h] = 0

    for i in reversed(range(1, h + 1)):
        for a, b in magic.values():
            
            
            rest = max(0, i - a)
            if dp[rest] > dp[i] + b:
                dp[rest] = dp[i] + b

    print(dp[0])


submit()

Solution (Python):

import sys
import collections as cl
import math


def II(): return int(sys.stdin.readline())


def MI(): return map(int, sys.stdin.readline().split())


def LI(): return list(map(int, sys.stdin.readline().split()))


def main():
    h, n = MI()
    a = []
    b = []
    for _ in range(n):
        _a, _b = MI()
        a.append(_a)
        b.append(_b)

    max_a = max(a)

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

    for i in range(1, h + max_a + 1):
        min_itr = 10**19

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

            else:
                min_itr = min(min_itr, b[j])

        dp[i] = min_itr

    print(min(dp[h:h+max_a]))


main()

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

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

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

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

inf = 10 ** 9
dp = [0] + [inf] * H

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

print(dp[H])

Solution (Python):
h,n=map(int,input().split())
magic=[list(map(int,input().split())) for _ in range(n)]
dp=[10**9]*(h+10**5)

dp[0]=0
for i in range(h):
    for damage,cost in magic:
        dp[i+damage]=min(dp[i+damage],dp[i]+cost)
ans=10**9
for i in range(10**5):
    ans=min(ans,dp[i+h])
print(ans)

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


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

for (A,B) in L:
    for k in range(1,H+1):
        if k>=A:
            DP[k]=min(DP[k],DP[k-A]+B)
        else:
            DP[k]=min(DP[k],B)

print(DP[-1])

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




dp = [10**9] * (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())
a = [0 for i in range(n)]
b = [0 for i in range(n)]
for i in range(n):
    ai ,bi = map(int,input().split())
    a[i] = ai
    b[i] = bi


mh = [0 for i in range(10003)]
for i in range(1,h+1):
    mb = 10**9
    for j in range(n):
        if mb > mh[i-a[j]] + b[j]:
            mb = mh[i-a[j]] + b[j]
    mh[i] = mb

print(mh[h])

Solution (Python):
'''
自宅用PCでの解答
'''
import math

import itertools
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit


ipt = stdin.readline
setrecursionlimit(10**7)
mod = 10**9+7
dir = [(-1,0),(0,-1),(1,0),(0,1)]
alp = "abcdefghijklmnopqrstuvwxyz"

def main():
    h,n = map(int,ipt().split())
    atks = [tuple(map(int,ipt().split())) for i in range(n)]
    dam = [10**18]*(h+1)
    dam[0] = 0
    for i in range(1,h+1):
        for aj,bj in atks:
            if aj > i:
                if dam[i] > bj:
                    dam[i] = bj
            elif dam[i] > dam[i-aj]+bj:
                dam[i] = dam[i-aj]+bj

    print(dam[h])

    return None

if __name__ == '__main__':
    main()

Solution (Python):
def main():
    h, n = map(int, input().split())
    arr = [list(map(int, input().split())) for _ in range(n)]
    dp = [[float("inf")]*(2*10**4+1) for _ in range(n+1)]
    dp[0][0] = 0
    for i in range(n):
        p, a, b = i+1, arr[i][0], arr[i][1]
        for j in range(2*10**4+1):
            if j < a:
                dp[p][j] = dp[p-1][j]
            else:
                if dp[p][j-a] + b < dp[p-1][j]:
                    dp[p][j] = dp[p][j-a] + b
                else:
                    dp[p][j] = dp[p-1][j]
    print(min(dp[-1][h:2*10**4+1]))

if __name__ == "__main__":
    main()

Solution (Python):
(h, n), *m = [[*map(int, i.split())] for i in open(0)]
dp = [0] * 20001
for i in range(1, h + 1):
    dp[i] = min(dp[i-a]+b for a, b in m)
print(dp[h])

Solution (Python):
(h, n), *m = [[*map(int, i.split())] for i in open(0)]
dp = [0] * 20001
for i in range(1, h + 1):
    dp[i] = min(dp[i-a]+b for a, b in m)
print(dp[h])

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

Solution (Python):
import sys
from itertools import islice


def resolve(in_):
    H, N = map(int, next(in_).split())
    AB = tuple(tuple(map(int, line.split())) for line in islice(in_, N))
    
    dp = [1 << 31] * (H + 1)
    dp[0] = 0

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

    return dp[H]


def main():
    answer = resolve(sys.stdin.buffer)
    print(answer)


if __name__ == '__main__':
    main()

Solution (Python):
import sys
input = sys.stdin.readline
def main():
    H, N = map(int, input().split())
    A = []
    B = []
    for _ in range(N):
        a, b = map(int, input().split())
        A.append(a)
        B.append(b)
    A_max = max(A)
    dp = [1e14] * (H+A_max + 1) 
    dp[0] = 0
    for i in range(H):
        for j in range(N):
            dp[i+A[j]] = min(dp[i+A[j]], dp[i]+B[j])

    ans = 1e30
    for i in range(H, H+A_max+1):
        ans = min(ans, dp[i])
    print(ans)
main()

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

Solution (Python):
h,n = map(int,input().split())
M = []
max_val = 0
for _ in range(n):
    a,b = map(int,input().split())
    max_val = max(max_val,a)
    M.append((a,b))
dp = [float('inf')]*(h+1+max_val)
dp[0] = 0
for i in range(1,h+1+max_val):
    for j in range(n):
            dp[i] = min(dp[i-M[j][0]] + M[j][1],dp[i])
print(min(dp[h:-1]))

Solution (Python):
h,n=map(int,input().split())
a=[]
b=[]
for _ in range(n):
  x,y=map(int,input().split())
  a.append(x)
  b.append(y)
a_=max(a)
dp=[10**8]*(h+1+a_)
dp[0]=0
for i in range(1,len(dp)):
  for j in range(n):
    if 0<=i-a[j]<=len(dp)-1-a[j]:
      dp[i]=min(dp[i],dp[i-a[j]]+b[j])
print(min(dp[h:]))

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

Solution (Python):
import sys

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

for i in range(N):
    a, b = map(int, sys.stdin.readline().rstrip().split())
    A[i] = a
    B[i] = b

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

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

print(min(dp[H:H + max_A]))

Solution (Python):
import sys


def main():
    input = sys.stdin.buffer.readline
    h, n = map(int, input().split())
    a = [0] * n
    b = [0] * n
    for i in range(n):
        a[i], b[i] = map(int, input().split())
    max_a = max(a)
    
    dp = [1e9] * (h + max_a + 1)
    dp[0] = 0
    for i in range(n):
        for j in range(1, h + max_a + 1):
            dp[j] = min(dp[j], dp[max(j - a[i], 0)] + b[i])
    print(min(dp[h:]))


if __name__ == "__main__":
    main()

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

Solution (Python):
def numba_compile(numba_config):
    import os, sys
    if sys.argv[-1] == "ONLINE_JUDGE":
        from numba import njit
        from numba.pycc import CC
        cc = CC("my_module")
        for func, signature in numba_config:
            vars()[func.__name__] = njit(signature)(func)
            cc.export(func.__name__, signature)(func)
        cc.compile()
        exit()
    elif os.name == "posix":
        exec(f"from my_module import {','.join(func.__name__ for func, _ in numba_config)}")
        for func, _ in numba_config:
            globals()[func.__name__] = vars()[func.__name__]
    else:
        from numba import njit
        for func, signature in numba_config:
            globals()[func.__name__] = njit(signature, cache=True)(func)
        print("compiled!", file=sys.stderr)


import numpy as np

def solve(H, N, AB):
    
    dp = np.empty(H+1, dtype=np.int64)
    dp[:] = 1<<60
    dp[0] = 0
    for n in range(1, N+1):
        a, b = AB[n-1]
        for h in range(H):
            dp[min(H, h+a)] = min(dp[min(H, h+a)], dp[h]+b)
    return dp[-1]

numba_compile([
    [solve, "i8(i8,i8,i8[:,:])"],
])

import sys
def main():
    H, N = map(int, input().split())
    AB = np.array(sys.stdin.read().split(), dtype=np.int64).reshape(N, 2)
    ans = solve(H, N, AB)
    print(ans)

main()

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)

a_max = max(a)
dp = [0]*(h+a_max)

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

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

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

A, B = [0]*N, [0]*N


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

maxDamage = H + max(A)

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

for i in range(N):
    for j in range(maxDamage+1):

        if j < A[i]:
            dp[i+1][j] = dp[i][j]

        else:
            res1 = dp[i][j]
            res2 = dp[i+1][j - A[i]] + B[i]

            dp[i+1][j] = min(res1, res2)


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

Solution (Python):
import sys

import numba as nb
import numpy as np

input = sys.stdin.readline


@nb.njit("i8(i8,i8,i8[:,:])", cache=True)
def solve(H, N, AB):
    INF = 10 ** 18
    dp = np.full(shape=(H + 1), fill_value=INF, dtype=np.int64)
    dp[0] = 0
    for i in range(N):
        A, B = AB[i]
        for d in range(H + 1):
            if d < A:
                dp[d] = min(dp[d], B)
            else:
                dp[d] = min(dp[d], dp[d - A] + B)

    ans = dp[-1]
    return ans


def main():
    H, N = map(int, input().split())
    AB = np.zeros(shape=(N, 2), dtype=np.int64)
    for i in range(N):
        AB[i] = input().split()

    ans = solve(H, N, AB)
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
import sys

import numba as nb
import numpy as np

input = sys.stdin.readline


@nb.njit("i8(i8,i8,i8[:,:])", cache=True)
def solve(H, N, AB):
    INF = 10 ** 18
    dp = [INF] * (H + 1)
    dp[0] = 0
    for i in range(N):
        A, B = AB[i]
        for d in range(H + 1):
            if d < A:
                dp[d] = min(dp[d], B)
            else:
                dp[d] = min(dp[d], dp[d - A] + B)

    ans = dp[-1]
    return ans


def main():
    H, N = map(int, input().split())
    AB = np.zeros(shape=(N, 2), dtype=np.int64)
    for i in range(N):
        AB[i] = input().split()

    ans = solve(H, N, AB)
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
h,n=map(int,input().split())
a_=0
magic=[]
for i in range(n):
  a,b=map(int,input().split())
  a_=max(a,a_)
  c=[a,b]
  magic.append(c)
dp=[10**8+1]*(h+a_+1)
dp[0]=0
for i in range(n):
  a,b=magic[i]
  for j in range(len(dp)):
    if j+a<=h+a_:
      dp[j+a]=min(dp[j+a],dp[j]+b)
print(min(dp[h:]))

Solution (Python):
H,N =[int(i) for i in input().split()]
AAA = []
BBB = []
for i in range(N):
    buff = [int(i) for i in input().split()]
    AAA.append(buff[0])
    BBB.append(buff[1])


dp = [10000000000 for i in range(H+5)]
dp[0] = 0
for i in range(H+5):
    for j in range(N):
        A = AAA[j]
        B = BBB[j]
        if i-A>=0:
            dp[i]=min(dp[i],dp[i-A]+B)
        else:
            dp[i]=min(dp[i],B)


print(dp[H])

Solution (Python):
from collections import defaultdict
(h,n),*ab = [list(map(int, s.split())) for s in open(0)]

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

dp = defaultdict(lambda: float('inf'))
dp[0] = 0

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

print(min(v for k,v in dp.items() if k>=h))

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

Solution (Python):
def resolve():
    H, N = list(map(int, input().split()))
    AB = [list(map(int, input().split())) for i in range(N)]
    maxa = max([ab[0] for ab in AB])
    dp = [-1 for _ in range(H+maxa+1)]
    dp[0] = 0
    for i in range(H+1):
        if dp[i] == -1:
            continue
        for a, b in AB:
            dp[i+a] = min(dp[i+a], dp[i]+b) if dp[i+a] != -1 else dp[i]+b
    print(min(filter(lambda x: x != -1, dp[H:])))

    
    
if __name__ == "__main__":
    resolve()

Solution (Python):

H, N = map(int, input().split(' '))
nums = [float('inf') for _ in range(H+1)]
nums[0] = 0

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

print(nums[H])

Solution (Python):
import sys,math,collections,itertools
input = sys.stdin.readline

H,N=list(map(int,input().split()))
AB = []
amax = 0
for _ in range(N):
    a,b=map(int,input().split())
    amax = max(amax,a)
    AB.append([a,b])
HN = [float('inf')]*(H+amax+1)
HN[0] = 0
for i in range(H+amax+1):
    for j in range(N):
        if AB[j][0]<=i:
            tmp = HN[i-AB[j][0]]+AB[j][1]
            HN[i] = min(HN[i],tmp)
        else:
            tmp = AB[j][1]
            HN[i] = min(HN[i],tmp)
print(min(HN[H:]))

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

for i in range(h):
    for a,b in l:
        dp[i+a]=min(dp[i+a],dp[i]+b)
ans=10**9
for i in range(10**5):
    ans=min(ans,dp[i+h])
print(ans)