CodeEff/ECCO huggingface dataset:
# Original solution
h, n = list(map(int, input().split()))
dp = [0] + [float('inf')] * h
for i in range(n):
    a, b = list(map(int, input().split()))
    for j in range(h):
        nj = min(j + a, h)
        dp[nj] = min(dp[nj], dp[j] + b)
print((dp[h]))

# Optimized solution
h, n = list(map(int, input().split()))
magics = [list(map(int, input().split())) for _ in range(n)]
max_a = max(a for a, b 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((dp[h]))
# Original solution
H, N = list(map(int, input().split()))

inf = float('inf')
dp = [inf] * (H + 1)
dp[0] = 0
for _ in range(N):
    A, B = list(map(int, input().split()))
    for i in range(H):
        t1 = i + A
        if t1 > H:
            t1 = H
        t2 = dp[i] + B
        if t2 < dp[t1]:
            dp[t1] = t2
print((dp[H]))


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

inf = float('inf')
dp = [inf] * (H + 1)
dp[0] = 0
for _ in range(N):
    A, B = list(map(int, input().split()))
    for i in range(H):
        t1 = i + A
        if t1 > H:
            t1 = H
        t2 = dp[i]
        if t2 == inf:
            continue
        t2 += B
        if t2 < dp[t1]:
            dp[t1] = t2
print((dp[H]))
# Original solution
#!python3

from heapq import heappush, heappop, heapify

iim = lambda: list(map(int, input().rstrip().split()))

def resolve():
    H, N = iim()
    AB = [tuple(iim()) for i in range(N)]

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

    S = []
    for a, b in AB:
        n, m = divmod(H, a)
        i = 1
        while n >= i:
            S.append((a*i, b*i))
            n -= i
            i <<= 1
        if m:
            n += 1
        if n:
            S.append((a*n, b*n))

    N2 = len(S)
    def ubound(b, a, i):
        for j in range(i, N2):
            aj, bj = S[j]
            if a + aj >= H:
                return (b+bj, b + (H-a) * bj / aj)
            a += aj
            b += bj

        return (inf, inf)

    q = []
    u0, u1 = ubound(0, 0, 0)

    inf = float("inf")
    heappush(q, (u1, u0, 0, 0, 0))
    um = u0
    #print(AB)
    #print(H, S)
    while q:
        #print(q)
        uq0, uq1, aq, bq, i = heappop(q)

        if uq0 >= um:
            break

        if i >= N2: continue

        ai, bi = S[i]
        if aq + ai < H:
            heappush(q, (uq0, uq1, aq + ai, bq + bi, i + 1))

        u0, u1 = ubound(bq, aq, i + 1)
        if u1 <= um:
            if u0 < um:
                um = u0
            heappush(q, (u1, u0, aq, bq, i + 1))

    print(um)



if __name__ == "__main__":
    resolve()



# Optimized solution
#!python3
import sys
sys.setrecursionlimit(1000000)

from heapq import heappush, heappop, heapify

iim = lambda: list(map(int, input().rstrip().split()))

def resolve():
    H, N = iim()
    AB = [tuple(iim()) for i in range(N)]
    inf = float("inf")
    AB.sort(key=lambda a: (a[0]/a[1], -a[0]), reverse=True)

    def memo(f):
        cache = {}
        def wrapper(*a):
            if a in cache:
                return cache[a]
            b = f(*a)
            cache[a] = b

            return b

        return wrapper

    @memo
    def calc(h):
        if h <= 0: return 0

        bi = inf
        for a, b in AB:
            bj = b + calc(h - a)
            if bi > bj:
                bi = bj
            else:
                break
        return bi

    print((calc(H)))



if __name__ == "__main__":
    resolve()
# Original solution
def main():
    INF = float('inf')
    H,N = list(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+1)
    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()

# Optimized solution
def main():
    H,N = list(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)
    for i in range(0,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()
# Original solution
def main():
    INF = float('inf')
    H,N = list(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()


# Optimized solution
def main():
    INF = 10**9
    H,N = list(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()
# Original solution
import math

#Input
H, N = list(map(int, input().split()))
lstV = list()
lstC = list()
for i in range(N):
    value, cost = list(map(int, input().split()))
    lstV.append(value)
    lstC.append(cost)

#DPMap
inf = 2**31 - 1
dp = list([inf]*(H + max(lstV)))
dp[0] = 0
for i in range(0,len(dp)):
    if dp[i] != inf:
        for j in range(0,len(lstV)):
            value = lstV[j]
            cost = lstC[j]
            if i + value <= len(dp) - 1:
                dp[i + value] = min(dp[i + value], dp[i] + cost)
print((min(dp[H:])))

# Optimized solution
H, N = list(map(int, input().split()))
AB = list(list(map(int, input().split())) for _ in range(N))

def main2(H, N, AB):
    inf = 2**31 -1
    dp = [inf] * (H + max(a for a, _ in AB))
    dp[0] = 0
    for i in range(1, len(dp)):
        dp[i] = min(dp[i-a]+b for a,b in AB)
    print((min(dp[H:])))

main2(H,N,AB)
# Original solution
H, N = list(map(int, input().split()))

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

for n in range(1, N + 1):
    a, b = list(map(int, input().split()))
    for h in range(1, H + 1):
        tmp_min = dp[n - 1][h]
        i = 1
        while True:
            if h - i * a <= 0:
                tmp_min = min(tmp_min, dp[n - 1][0] + i * b)
                break
            tmp_min = min(tmp_min, dp[n - 1][h - i * a] + i * b)
            i += 1
        dp[n][h] = tmp_min

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


# Optimized solution
H, N = list(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]))
# Original solution
import math

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

#print(a)
#print(b)
INF = int(1e10)
dp = [[INF] * (h+1) for i in range(n+1)]
for i in range(h+1):
    dp[0][i] = math.ceil(i / a[0]) * b[0]
for i in range(n):
    dp[i][0] = 0
for i in range(n):
    for j in range(h+1):
        if j < a[i]:
            dp[i+1][j] = min(math.ceil(j / a[i]) * b[i], dp[i][j])
        else:
            dp[i+1][j] = min(math.ceil(j/ a[i]) * b[i], dp[i][j], dp[i+1][j - a[i]] + b[i])
#print(dp)
print((dp[n][h]))

# Optimized solution
import math

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

#print(a)
#print(b)
INF = int(1e10)
dp = [[INF] * (h+1) for i in range(n+1)]
for i in range(h+1):
    dp[0][i] = math.ceil(i / a[0]) * b[0]
for i in range(n):
    dp[i][0] = 0
for i in range(n):
    for j in range(h+1):
        if j < a[i]:
            dp[i+1][j] = min(-(-j // a[i]) * b[i], dp[i][j])
        else:
            dp[i+1][j] = min(-(-j // a[i]) * b[i], dp[i][j], dp[i+1][j - a[i]] + b[i])
#print(dp)
print((dp[n][h]))
# Original solution
h, n = list(map(int, input().split()))
x = [list(map(int, input().split())) for _ in range(n)]
a, b = x[0]
dp = [-(-i // a) * b for i in range(h + 1)]
for j in range(1, n):
    a, b = x[j]
    for i in range(h + 1):
        if i >= a:
            dp[i] = min(dp[i], dp[i - a] + b)
        else:
            dp[i] = min(dp[i], b)
print((dp[-1]))


# Optimized solution
h, n = list(map(int, input().split()))
x = [list(map(int, input().split())) for _ in range(n)]
a, b = x[0]
dp = [-(-i // a) * b for i in range(h + 1)]
for j in range(1, n):
    a, b = x[j]
    for i in range(min(h + 1, a)):
        dp[i] = min(dp[i], b)
    for i in range(a, h + 1):
        dp[i] = min(dp[i], dp[i - a] + b)
print((dp[-1]))
# Original solution
#import sys
MOD = 10 ** 9 + 7
INFI = 10**10
#input = sys.stdin.readline
import math

import itertools

#import bisect

import copy
from functools import lru_cache

def sosuhante(n):
    for k in range(2, int(math.sqrt(n))+1):
        if n% k ==0:
            return False
    return True
def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

def kingaku(a,b,n):
    keta=len(str(n))
    return a*n+b*keta

def my_index(l, x, default=False):
    if x in l:
        return l.index(x)
    else:
        return default

#    h,w,a,b = map(int, input().split())
#    c = [[0 for j in range(n)] for i in range(n)]



def main():
    h,n=list(map(int,input().split())) #n yen, m types
    ab=[list(map(int,input().split())) for i in range(n)]
    maxa = max(a for a, b in ab)
    dp=[INFI for i in range(h+maxa)]
    dp[0]=0


    def f(h):

        for a,b in ab:
            for j in range(h+maxa):
                dp[j]=min(dp[j],dp[j-a]+b)
        return min(dp[h:])

    print((f(h)))


if __name__ == "__main__":
    main()

# Optimized solution
#import sys
MOD = 10 ** 9 + 7
INFI = 10**10
#input = sys.stdin.readline
import math
 
import itertools
 
#import bisect
 
import copy
 
 
def sosuhante(n):
    for k in range(2, int(math.sqrt(n))+1):
        if n% k ==0:
            return False
    return True
def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n
 
    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]
 
    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot
 
    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])
 
    return result
 
def kingaku(a,b,n):
    keta=len(str(n))
    return a*n+b*keta
 
def my_index(l, x, default=False):
    if x in l:
        return l.index(x)
    else:
        return default
 
#    h,w,a,b = map(int, input().split())
#    c = [[0 for j in range(n)] for i in range(n)]
 
 
 
def main():
    h,n=list(map(int,input().split())) #n yen, m types
    a=[]
    b=[]
    for i in range(n):
        x,y=list(map(int,input().split()))
        a.append(x)
        b.append(y)
 
    dp=[INFI for i in range(h+1)]
    dp[0]=0
    for i in range(n):
        for j in range(len(dp)):
            if j-a[i]<0:
                dp[j] = min(dp[j], dp[0] + b[i])
            else:
                dp[j]=min(dp[j],dp[j-a[i]]+b[i])
 
    print((dp[h]))
 
 
if __name__ == "__main__":
    main()
# Original solution
# ダイナミック・プログラミング
# PythonではTLEを起こしてしまう例

INF = float('inf')

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

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

dp = [[INF]*(H+1) for i in range(N+1)] # DP用配列
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]))


# Optimized solution
# Problem E - Crested Ibis vs Monster

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

# initialization
dp = [float('INF')]*(H+1)
dp[0] = 0
mg_len = len(magic_list)

# dp
for i in range(1, H+1):
    for j in range(mg_len):
        a = magic_list[j][0]
        b = magic_list[j][1]
        last_p = i - a
        if last_p<0:
            last_p = 0
        tmp = dp[last_p] + b
        dp[i] = min(dp[i], tmp)

# output
print((dp[H]))
# Original solution
def chmin(dp, i, *x):
  dp[i] = min(dp[i], *x)
INF = float("inf")

# dp[i] := min 消耗する魔力 to H -= i
h, n = list(map(int, input().split()))
dp = [0] + [INF]*h
for _ in [None]*n:
  a, b = list(map(int, input().split()))
  for j in range(h + 1):
    chmin(dp, min(j + a, h), dp[j] + b)
print((dp[h]))

# Optimized solution
(h,n),*t=[list(map(int,o.split()))for o in open(0)]
d=[0]+[9e9]*h
for a,b in t:
 for j in range(h+1):d[j]=min(d[j],d[max(0,j-a)]+b)
print((d[h]))
# Original solution
h,n=list(map(int,input().split()))
INF=10**9
dp=[INF]*(h+10)
A=[list(map(int,input().split())) for i in range(n)]
dp[0]=0
for a,b in A:
  for i in range(h):
    index=min(h,i+a)
    x=dp[i]+b; y=dp[index]
    dp[index]=min(x,y)
print((dp[h]))


# Optimized solution
h,n=list(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:])))
# Original solution
H, N = list(map(int, input().split()))
M = [tuple(map(int, input().split())) for i in range(N)]

dp = [(i + M[0][0] - 1) // M[0][0] * M[0][1] for i in range(H + 1)]
for i in range(N):
    Ai, Bi = M[i]
    ndp = [0] * (H + 1)
    if Ai >= H:
        ndp[0:H + 1] = [min(dp[j], Bi) for j in range(H + 1)]
    else:
        ndp[0:Ai + 1] = [min(dp[j], Bi) for j in range(Ai + 1)]
        for j in range(Ai + 1, H + 1):
            ndp[j] = min(dp[j], ndp[j - Ai] + Bi)
    dp = ndp
print((dp[H]))


# Optimized solution
H, N = list(map(int, input().split()))
M = [tuple(map(int, input().split())) for i in range(N)]

dp = [(j + M[0][0] - 1) // M[0][0] * M[0][1] for j in range(H + 1)]
for i in range(1, N):
    Ai, Bi = M[i]
    ndp = [0] * (H + 1)
    if Ai >= H:
        ndp[0:H + 1] = [min(dp[j], Bi) for j in range(H + 1)]
    else:
        ndp[0:Ai + 1] = [min(dp[j], Bi) for j in range(Ai + 1)]
        for j in range(Ai + 1, H + 1):
            ndp[j] = min(dp[j], ndp[j - Ai] + Bi)
    dp = ndp
print((dp[H]))
# Original solution
H, N = list(map(int, input().split()))
A=[]
B=[]
for i in range(N):
	a,b = list(map(int, input().split()))
	A.append(a)
	B.append(b)
#dp[i+1][h] := i番目の魔法まで見て、ライフをh以上削った時の最小魔力コスト
dp=[[float("inf")]*(H+1) for _ in range(N+1)]

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

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

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

dp=[[float("inf")]*(H+1) for _ in range(N+1)]
dp[0][0]=0
for i in range(N):
	a, b = A[i], B[i]
	for j in range(H+1):
		if a>=j:
			dp[i+1][j] = min(dp[i][j], b)
		else:
			dp[i+1][j] = min(dp[i][j], dp[i+1][j-a]+b)
print((dp[-1][-1]))
# Original solution
H, N = list(map(int, input().split()))
a = [None] * (N + 1)
b = [None] * (N + 1)
for i in range(1, N + 1):
    a[i], b[i] = list(map(int, input().split()))

# dp[i][j] = 魔法iまでからダメージの総和がj以上になるように選んだ時の魔力の最小値
# dp[i][j] = min(dp[i][j - a] + b, dp[i - 1][j])

dp = [[float('inf') for _ in range(H + 1)] for _ 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(H + 1):
        dp[i][j] = min(dp[i][max(0, j - a[i])] + b[i], dp[i - 1][j])
print((dp[N][H]))


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

# dp[i][j] = 魔法iまでからダメージの総和がj以上になるように選んだ時の魔力の最小値
# dp[i][j] = min(dp[i][j - a] + b, dp[i - 1][j])

dp = [[float('inf')] * (H + 1)] * (N + 1)
for i in range(N + 1):
    dp[i][0] = 0
for i in range(1, N + 1):
    a, b = list(map(int, input().split()))
    for j in range(H + 1):
        dp[i][j] = min(dp[i][max(0, j - a)] + b, dp[i - 1][j])
print((dp[N][H]))
# Original solution
H,N=list(map(int,input().split()))
ab=[list(map(int,input().split()))for _ in range(N)]
from heapq import*

count=[0]+[1]*H
ans=[10**9]*(H+1)
ans[0]=0
que=[0]
heapify(que)
while que:
    x=heappop(que)
    for a,b in ab:
        a=min(a,H-x)
        if ans[x+a]>ans[x]+b:
            ans[x+a]=ans[x]+b
            if count[x+a]:
                heappush(que,x+a)
                count[x+a]=0

print((ans[H]))

# Optimized solution
H,N=list(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]))
# Original solution
H,N=list(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]))

# Optimized solution
h,n=list(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]))
# Original solution
h,n=list(map(int,input().split()))
c=[list(map(int,input().split()))for _ in range(n)]
d=[0]+[10**9]*h
for i in range(h):
    #d[i]=min(d[i-a]+b for a,b in c)
    for a,b in c:
        a=min(a,h-i)
        d[i+a]=min(d[i+a],d[i]+b)
print((d[h]))

# Optimized solution
h,n=list(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]))
# Original solution
h,n=list(map(int,input().split()))
a=[0]
b=[0]
width=2*10**4+7
dp=[[10**10 for i in range(width)] for j in range(n+1)]
dp[0][0]=0
dp[1][0]=0
for i in range(n):
    x,y=list(map(int,input().split()))
    a.append(x)
    b.append(y)
for i in range(1,n+1):
    for j in range(width):
        dp[i][j]=min(dp[i][j],dp[i-1][j])
        if(j+a[i]<width):
            dp[i][j+a[i]]=min(dp[i][j+a[i]],dp[i][j]+b[i])
print((min(dp[n][h:])))

# Optimized solution
h,n=list(map(int,input().split()))
dp=[10**10 for i in range(h+1)]
dp[0]=0
for i in range(n):
    x,y=list(map(int,input().split()))
    for j in range(h+1):
        nj=min(h,j+x)
        dp[nj]=min(dp[nj],dp[j]+y)
print((dp[h]))
# Original solution
w, h = (int(x) for x in input().split())
ab = []
for _ in range(h):
    a, b = (int(x) for x in input().split())
    ab.append([a, b])

dp = [10000000000000 for i in range(w+1)]

for j in range(w+1):
    for i in range(h):
        if j <= ab[i][0]:
            dp[j] = min(dp[j], ab[i][1])
        else:
            dp[j] = min(dp[j], dp[j-ab[i][0]]+ab[i][1])

print((dp[w]))

# Optimized solution
w, h = (int(x) for x in input().split())
ab = []
for _ in range(h):
    a, b = (int(x) for x in input().split())
    ab.append([a, b])

dp = [0] * (w + max(a for a, b in ab))

for j in range(1, w+1):
    dp[j] = min(dp[j-a]+b for a, b in ab)

print((dp[w]))
# Original solution
h,n = list(map(int,input().split()))
ab = []
for _ in range(n):
    a, b = (int(x) for x in input().split())
    ab.append([a, b])

dp = [[100000000 for i in range(h+1)] for j in range(n+1)]

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

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

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

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

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

for y in range(N):
    a,b = AB[y]
    for x in range(H+1):
        if x <= a:
            dp[y+1][x] = min(dp[y][x], b)
        else:
            dp[y+1][x] = min(dp[y][x], dp[y+1][x-a]+b)
print((dp[-1][-1]))
# Original solution
H, N = list(map(int, input().split()))
A = []
B = []
for _ in range(N):
    a, b = list(map(int, input().split()))
    A.append(a)
    B.append(b)

mA = max(A)

INF = 1001001001
DP = [INF for _ in range(H+1)]
DP[0] = 0
ans = INF
for h in range(H):
    for j in range(N):
        DP[min(h+A[j], H)] = min(DP[min(h+A[j], H)], DP[h] + B[j])
    if DP[H] < ans:
        ans = DP[H]

print(ans)

# Optimized solution
H, N = list(map(int, input().split()))
A = []
B = []
for _ in range(N):
    a, b = list(map(int, input().split()))
    A.append(a)
    B.append(b)

mA = max(A)

INF = 1001001001
DP = [INF for _ in range(H+1)]
DP[0] = 0
for h in range(H):
    for j in range(N):
        nh = min(h+A[j], H)
        DP[nh] = min(DP[nh], DP[h] + B[j])

print((DP[H]))
# Original solution
from math import ceil
H,N = list(map(int, input().split()))
A = []
for _ in range(N):
  A.append(list(map(int, input().split())))
  
# 1回iを使ってから、のこりをjで仕留める、を全探索でよい気がする
# だめだった

# dp[i] : HPをi減らすために必要なmin魔力
dp = [1e9] * (10010)
dp[0] = 0
for i in range(1,H+1):
  for a in A:
    ap, mp = a
    down = max(0, i - ap)
    dp[i] = min(dp[i], min(dp[down:i]) + mp)
      
print((dp[H]))

# Optimized solution
from math import ceil
H,N = list(map(int, input().split()))
A = []
for _ in range(N):
  A.append(list(map(int, input().split())))
  
# 1回iを使ってから、のこりをjで仕留める、を全探索でよい気がする
# だめだった

# dp[i] : HPをi減らすために必要なmin魔力
dp = [1e9] * (10010)
dp[0] = 0
for i in range(1,H+1):
  for a in A:
    ap, mp = a
    down = max(0, i - ap)
    dp[i] = min(dp[i], dp[down] + mp)
      
print((min(dp[H:])))
# Original solution
#input
H, N = list(map(int, input().split()))
A = []
B = []
for _ in range(N):
    a, b = list(map(int, input().split()))
    A.append(a)
    B.append(b)

#output
M = max(A)
inf = 10**10
dp = [inf]*(H+(M+1))
dp[0] = 0
for i in range(N):
    for j in range(A[i], H+M):
        dp[j] = min(dp[j], dp[j-A[i]] + B[i])

answer = min(dp[H:(H+M+1)])
print(answer)

# Optimized solution
#input
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()))

#output
M = max(A)
inf = 10**10
dp = [inf]*(H+(M+1))
dp[0] = 0
for i in range(N):
    for j in range(A[i], H+M):
        dp[j] = min(dp[j], dp[j-A[i]] + B[i])

answer = min(dp[H:(H+M+1)])
print(answer)
# Original solution
import bisect
H,N = [int(x) for x in input().split()]
AB = [[int(x) for x in input().split()] for _ in range(N)]
dp = [[10**18]*(10**4+1) for _ in range(N+1)]
for i in range(N+1):
  dp[i][0]=0
mi=10**9
for i in range(N):
  for w in range(10**4+1):
    dp[i+1][w]=min(dp[i+1][w],dp[i][w])
    if w-AB[i][0]>=0:
      dp[i+1][w]=min(dp[i+1][w],dp[i + 1][w - AB[i][0]] + AB[i][1])
for i in range(H,10**4+1):
  mi = min(mi,dp[N][i])
print(mi)

# Optimized solution
import bisect
H,N = [int(x) for x in input().split()]
AB = [[int(x) for x in input().split()] for _ in range(N)]
dp = [[10**18]*(H+1) for _ in range(N+1)]
dp[0][0]=0
mi=10**9
for i in range(N):
  for w in range(H+1):
    dp[i+1][w]=min(dp[i+1][w],dp[i][w])
    dp[i+1][min(w+AB[i][0],H)]=min(dp[i+1][min(w+AB[i][0],H)],dp[i+1][w]+AB[i][1])
print((dp[N][H]))
# Original solution
h, n = list(map(int, input().split()))
ab = list(list(map(int, input().split())) for _ in range(n) )

dp = [0] * (h + max(list( node[0] for node in ab )))

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

# Optimized solution
h, n = list(map(int, input().split()))
ab = list(list(map(int, input().split())) for _ in range(n) )

dp = [0] * (h + max(list( node[0] for node in ab )))

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