CodeEff/ECCO huggingface dataset:
# Original solution
import sys

sys.setrecursionlimit(500000)
h, n = 0, 0
ab = None
dp = dict()

def input() -> str:
    return sys.stdin.readline().rstrip()

def f(i, j):
    if j <= 0:
        return 0
    if i < 0 and j > 0:
        return float("inf")
    ij = n * j + i
    if ij not in dp:
        dp[ij] = min([f(i - 1, j - k * ab[i][0]) + k * ab[i][1] for k in range((h - 1) // ab[i][0] + 2)])
    return dp[ij]

def main():
    global h, n, ab
    h, n = list(map(int, input().split()))
    ab = sorted([tuple(map(int, input().split())) for _ in range(n)], key=lambda x: -x[0])
    print((f(n - 1, h)))

if __name__ == "__main__":
  main()

# Optimized solution
import sys

def input() -> str:
    return sys.stdin.readline().rstrip()

h, n = list(map(int, input().split()))
ab = [tuple(map(int, input().split())) for _ in range(n)]
m = max(a for a, _ in ab)
dp = [0] * (h + m * 2 + 1)
for i in range(-m, h + m + 1):
    if i <= 0:
        dp[i] = 0
    else:
        dp[i] = min(dp[i - a] + b for a, b in ab)
print((min(dp[h:h + m + 1])))
# Original solution
# AtCoder Beginner Contest 153
# E - Crested Ibis vs Monster
# https://atcoder.jp/contests/abc153/tasks/abc153_e
H, N, *A = list(map(int, open(0).read().split()))
*A, = list(zip(*[iter(A)]*2))

INF = 1 << 30
dp = [INF]*(H+1)
dp[0] = 0
for i, (a, b) in enumerate(A):
    for h in range(H+1):
        mh = min(H, h+a)
        dp[mh] = min(dp[mh], dp[h] + b)
print((dp[H]))


# Optimized solution
import sys
input = sys.stdin.buffer.readline
H, N = list(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]))
# Original solution
#from pprint import pprint
#from collections import deque
#from collections import defaultdict
#from collections import Counter
#from copy import deepcopy
#from itertools
#import sys 
#sys.setrecursionlimit(N) #N回まで再起を許可する。
 
# = map(int,input().split())
 
# = list(map(int,input().split()))
 
# = [list(map(int,input().split())) for _ in range(XXXX)]
from sys import stdin
input = stdin.readline
 
h,n = list(map(int,input().split()))
 
ab= [list(map(int,input().split())) for _ in range(n)]
 
dp = [[float("inf") for _ in range(h+1)] for _ in range(n+1)]
#dp[i][j]はi番目のものを選んだ時かつダメージ送料がjだったときの最小MP、
 
 
for i in range(1,n+1):
    dp[i][0] = 0
    for j in range(h+1):
        a = ab[i-1][0]
        b = ab[i-1][1]
        dp[i][j] = min(dp[i][j],dp[i-1][j])
        if j+a <= h:
            dp[i][j+a] = min(dp[i][j] + b, dp[i-1][j+a], dp[i][j+a])
        elif j+a > h:
            dp[i][h] = min(dp[i][j] + b, dp[i-1][h], dp[i][h])

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

#print(dp[-1])

# Optimized solution
#from pprint import pprint
#from collections import deque
#from collections import defaultdict
#from collections import Counter
#from copy import deepcopy
#from itertools
#import sys 
#sys.setrecursionlimit(N) #N回まで再起を許可する。
 
# = map(int,input().split())
 
# = list(map(int,input().split()))
 
# = [list(map(int,input().split())) for _ in range(XXXX)]
from sys import stdin


def main():
    input = stdin.readline
    
    h,n = list(map(int,input().split()))
    
    ab= [list(map(int,input().split())) for _ in range(n)]
    
    dp = [[float("inf") for _ in range(h+1)] for _ in range(n+1)]
    #dp[i][j]はi番目のものを選んだ時かつダメージ送料がjだったときの最小MP、
    
    
    for i in range(1,n+1):
        dp[i][0] = 0
        for j in range(h+1):
            a = ab[i-1][0]
            b = ab[i-1][1]
            dp[i][j] = min(dp[i][j],dp[i-1][j])
            if j+a <= h:
                dp[i][j+a] = min(dp[i][j] + b, dp[i-1][j+a], dp[i][j+a])
            elif j+a > h:
                dp[i][h] = min(dp[i][j] + b, dp[i-1][h], dp[i][h])

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

if __name__ == "__main__":
    main()
# Original solution
#from pprint import pprint
#from collections import deque
#from collections import defaultdict
#from collections import Counter
#from copy import deepcopy
#from itertools
#import sys 
#sys.setrecursionlimit(N) #N回まで再起を許可する。
 
# = map(int,input().split())
 
# = list(map(int,input().split()))
 
# = [list(map(int,input().split())) for _ in range(XXXX)]
from sys import stdin


def main():
    input = stdin.readline
    
    h,n = list(map(int,input().split()))
    
    ab= [list(map(int,input().split())) for _ in range(n)]
    
    dp = [[float("inf") for _ in range(h+1)] for _ in range(n+1)]
    #dp[i][j]はi番目のものを選んだ時かつダメージ送料がjだったときの最小MP、
    
    
    for i in range(1,n+1):
        dp[i][0] = 0
        for j in range(h+1):
            a = ab[i-1][0]
            b = ab[i-1][1]
            dp[i][j] = min(dp[i][j],dp[i-1][j])
            if j+a <= h:
                dp[i][j+a] = min(dp[i][j] + b, dp[i-1][j+a], dp[i][j+a])
            elif j+a > h:
                dp[i][h] = min(dp[i][j] + b, dp[i-1][h], dp[i][h])

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

if __name__ == "__main__":
    main()

# Optimized solution
#from pprint import pprint
#from collections import deque
#from collections import defaultdict
#from collections import Counter
#from copy import deepcopy
#from itertools
#import sys 
#sys.setrecursionlimit(N) #N回まで再起を許可する。
 
# = map(int,input().split())
 
# = list(map(int,input().split()))
 
# = [list(map(int,input().split())) for _ in range(XXXX)]
from sys import stdin


def main():
    input = stdin.readline
    
    h,n = list(map(int,input().split()))
    
    ab= [list(map(int,input().split())) for _ in range(n)]
    
    dp = [[100000001 for _ in range(h+1)] for _ in range(n+1)]
    #dp[i][j]はi番目のものを選んだ時かつダメージ送料がjだったときの最小MP、
    
    
    for i in range(1,n+1):
        dp[i][0] = 0
        for j in range(h+1):
            a = ab[i-1][0]
            b = ab[i-1][1]
            dp[i][j] = min(dp[i][j],dp[i-1][j])
            if j+a <= h:
                dp[i][j+a] = min(dp[i][j] + b, dp[i-1][j+a], dp[i][j+a])
            elif j+a > h:
                dp[i][h] = min(dp[i][j] + b, dp[i-1][h], dp[i][h])

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

if __name__ == "__main__":
    main()
# Original solution
H,N=list(map(int,input().split()))
ABC=[]
for _ in range(N):
  a,b=list(map(int,input().split()))
  ABC.append((a,b,a/b))
ABC=sorted(ABC, key=lambda x:x[2], reverse=True)
A=[ABC[i][0] for i in range(N)]
B=[ABC[i][1] for i in range(N)]
dp=[[float('inf')]*(H+1) for i in range(N+1)]
for i in range(N+1):
  dp[i][0]=0
  
for i in range(N):
  for j in range(1,H+1):
    if j-A[i]>=0:
      dp[i+1][j]=min(dp[i][j],dp[i+1][j-A[i]]+B[i])
    else:
      dp[i+1][j]=min(dp[i][j],dp[i+1][0]+B[i])
print((dp[N][H]))
#print(dp)

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

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

for i in range(h+1):
  if dp[i] == 10 ** 8 + 1:
      continue
  for j in range(n):
    x = dp[i] + l[j][1]
    if dp[i + l[j][0]] > x:
      dp[i + l[j][0]] = x

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


# Optimized solution
def main():
    from sys import stdin
    readline = stdin.readline
    H, N = list(map(int, readline().split()))
    AB = [list(map(int, readline().split())) for _ in range(N)]

    dp = [100000000] * (H + 10 ** 4 + 1)
    dp[0] = 0
    for i in range(H):
        if dp[i] == 100000000:
            continue
        for a, b in AB:
            t = dp[i] + b
            if t < dp[i + a]:
                dp[i + a] = t
    print((min(dp[H:])))


main()
# Original solution
from sys import stdin
readline = stdin.readline
H, N = list(map(int, readline().split()))
AB = [list(map(int, readline().split())) for _ in range(N)]

dp = [100000000] * (H + 10 ** 4 + 1)
dp[0] = 0
for i in range(H):
    if dp[i] == 100000000:
        continue
    for a, b in AB:
        t = dp[i] + b
        if t < dp[i + a]:
            dp[i + a] = t
print((min(dp[H:])))




# Optimized solution
def main():
  h, n = list(map(int, input().split()))
  l = [list(map(int, input().split())) for i in range(n)]

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

  for i in range(h):
    if dp[i] == 10 ** 8 + 1:
        continue
    for a, b in l:
      x = dp[i] + b
      if dp[i + a] > x:
        dp[i + a] = x

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

main()
# Original solution
INF = 10 ** 18


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

dp = [[INF] * (H + 1) for _ in range(N + 1)]
dp[0][0] = 0
for i in range(N):
    for j in range(H + 1):
        if j < AB[i][0]:
            dp[i + 1][j] = min(dp[i][j], dp[i + 1][0] + AB[i][1])
        else:
            dp[i + 1][j] = min(dp[i][j], dp[i + 1][j - AB[i][0]] + AB[i][1])
    
print((dp[N][H]))

# for d in dp:
#     print (d)

# Optimized solution
import sys
input = sys.stdin.readline

INF = 10 ** 18

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

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

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

# for d in dp:
#     print (d)
# Original solution
H,N=list(map(int,input().split()))
ab=[list(map(int,input().split())) for _ in range(N)]
x=max(a for a,b in ab)
dp=[0]*(H+x)
for i in range (1,H+x):
    dp[i]=min(dp[i-a]+b for a,b in ab)
print((dp[H]))

# Optimized solution
H,N=list(map(int,input().split()))
ab=[list(map(int,input().split())) for _ in range(N)]
x=max(a for a,b in ab)
dp=[0]*(H+x)
for i in range (1,H+1):
    dp[i]=min(dp[i-a]+b for a,b in ab)
print((dp[H]))
# Original solution
H,N=list(map(int,input().split()))
ab=[list(map(int,input().split())) for _ in range(N)]
x=max(a for a,b in ab)
dp=[0]*(H+1)
for i in range (1,H+1):
    dp[i]=min(dp[max(i-a,0)]+b for a,b in ab)
print((dp[H]))

# Optimized solution
H,N=list(map(int,input().split()))
ab=[list(map(int,input().split())) for _ in range(N)]
dp=[0]*(H+10**5)
for i in range (1,H+1):
    dp[i]=min(dp[i-a]+b for a,b in ab)
print((dp[H]))
# Original solution
H, N = list(map(int, input().split()))
magic = [list(map(int, input().split())) for i in range(N)]

# dp[damage] := モンスターに damage を与えるために必要な最小コスト

# damage = 0,1,2,...,H
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)
print((dp[-1]))


# Optimized solution
H, N = list(map(int, input().split()))
AB = []
for _ in range(N):
    A, B = list(map(int, input().split()))
    AB.append([A, B])
dp = [10**9] * (H + 1)
dp[0] = 0
for i in range(H):
    for a, b in AB:
        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]))
# Original solution
import math
h,n = list(map(int,input().split()))


ab = []
for i in range(n):
    ab.append([int(i) for i in input().split()])
ab.sort()

dp = []
for i in range(h + ab[n-1][0]):
    dp.append(pow(2, 31) - 1)
dp[0] = 0

for i in range(1, len(dp)):
    tmp = dp[i]
    for j in range(n):
        #print(j-ab[j][0])
        tmp = min(tmp, dp[max(0, i-ab[j][0])]+ab[j][1])
    dp[i] = tmp

#print(dp)
print((min(dp[h:])))

# Optimized solution
import math
h,n = list(map(int,input().split()))


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

dp = []
for i in range(h + max(a)):
    dp.append(pow(2, 31) - 1)
dp[0] = 0

for i in range(1, len(dp)):
    '''
    tmp = dp[i]
    for j in range(n):
        tmp = min(tmp, dp[max(0, i-a[j])] + b[j])
    dp[i] = tmp
    '''
    dp[i] = min(dp[i - A] + B for A, B in zip(a, b))

print((min(dp[h:])))
# Original solution
def num():
    from sys import stdin
    h, n = list(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 in magic:
                if i-j[0] < 0:
                    if ans[0] > ans[i]+j[1]:
                        ans[0] = ans[i]+j[1]
                elif ans[i-j[0]] > ans[i]+j[1]:
                    ans[i-j[0]] = ans[i]+j[1]
    return ans[0]
print((num()))




# Optimized solution
def num():
    from sys import stdin
    h, n = list(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 in magic:
                if i-j[0] < 0:
                    num = ans[i]+j[1]
                    if ans[0] > num:
                        ans[0] = num
                else:
                    num = ans[i]+j[1]
                    if ans[i-j[0]] > num:
                        ans[i-j[0]] = num
    return ans[0]
print((num()))
# Original solution
h,n=list(map(int,input().split()))
ab=[]
p=0
for i in range(n):
	a,b=list(map(int,input().split()))
	p=max(p,a)
	ab.append([a,b])
dp=[[10**9]*(p+1+h) for _ in range(n+1)]
for i in range(n+1):
	dp[i][0]=0

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

# Optimized solution
def main():
	inf=10**9
	h,n=list(map(int,input().split()))
	ab=[]
	r=0
	for i in range(n):
		a,b=list(map(int,input().split()))
		ab.append((a,b))
		r=max(r,a)
	#dp[number][damage]
	dp=[[inf for _ in range(r+h)]for _ in range(n+1)]
	for i in range(n+1):
		dp[i][0]=0
	for i in range(n):
		for j in range(r+h):
			if j-ab[i][0]>=0:
				dp[i+1][j]=dp[i+1][j-ab[i][0]]+ab[i][1]
			dp[i+1][j]=min(dp[i][j],dp[i+1][j])
	ans=inf
	for i in range(r):
		ans=min(ans,dp[n][i+h])
	print(ans)
if __name__ == '__main__':
	main()
# Original solution
import sys
input = sys.stdin.buffer.readline

H, N = list(map(int, input().split()))
AB = [list(map(int, input().split())) for _ in range(N)]
INF = 10 ** 15

dp = [INF] * (H + 1)
dp[0] = 0
for a, b in AB:
  for i in range(H):
    if dp[i] != INF:
      dp[min(i + a, H)] = min(dp[min(i + a, H)], dp[i] + b)

print((dp[-1]))

# Optimized solution
import sys
input = sys.stdin.buffer.readline

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

INF = 10 ** 15
dp = [INF] * H
dp[0] = 0

answer = INF
for a, b in AB:
  for i in range(H):
    if dp[i] != INF:
      if i + a < H:
        dp[i + a] = min(dp[i + a], dp[i] + b)
      else:
        answer = min(answer, dp[i] + b)

print(answer)
# Original solution
import math
H, N = tuple(map(int, input().split(" ")))
AB = []
for _ in range(N):
    AB.append(tuple(map(int, input().split(" "))))

minpower = 10 ** 10

# dp[n][h] = 0 ~ n - 1 番目の魔法を使えた時、残り体力がhのモンスターを倒すために必要な魔力
dp = [[minpower for _ in range(H + 1)] for __ in range(N)]
for h in range(H):
    dp[0][h] = math.ceil(h / AB[0][0]) * AB[0][1]

for n in range(N):
    dp[n][0] = 0

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

        if h - a < 0:
            dp[n][h] = min(
                dp[n-1][h],
                b
            )
        else:
            dp[n][h] = min(
                dp[n-1][h],
                dp[n][h-a] + b)
print((dp[-1][H]))

# Optimized solution
import math
H, N = tuple(map(int, input().split(" ")))
AB = []
for _ in range(N):
    AB.append(tuple(map(int, input().split(" "))))

minpower = 10 ** 8 + 1

# dp[n][h] = 0 ~ n - 1 番目の魔法を使えた時、残り体力がhのモンスターを倒すために必要な魔力
dp = [[minpower for _ in range(H + 1)] for __ in range(N)]
for h in range(H):
    dp[0][h] = math.ceil(h / AB[0][0]) * AB[0][1]

for n in range(N):
    dp[n][0] = 0

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

        if h - a < 0:
            dp[n][h] = min(
                dp[n-1][h],
                b
            )
        else:
            dp[n][h] = min(
                dp[n-1][h],
                dp[n][h-a] + b)
print((dp[-1][H]))
# Original solution
INF = 10**12
maxH = 2 * 10**4 + 10

def solve():
    H, N = list(map(int, input().split()))
    ABs = [tuple(map(int, input().split())) for _ in range(N)]

    dp = [INF] * (maxH+1)
    dp[0] = 0
    for A, B in ABs:
        for h in range(maxH-A+1):
            h2 = h + A
            dp2 = dp[h] + B
            if dp2 < dp[h2]:
                dp[h2] = dp2

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


solve()


# Optimized solution
import sys
input = sys.stdin.readline

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

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

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

    items.sort()

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

    print((dp[H]))


solve()
# Original solution
import sys
import math  # noqa
import bisect  # noqa
import queue  # noqa


def input():
    return sys.stdin.readline().rstrip()


def main():
    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)

    INF = 1000000005
    dp = [INF for _ in range(H + 1)]
    dp[0] = 0
    for i in range(0, H + 1):
        for j in range(N):
            k = 0
            while i + k * A[j] < H:
                dp[i + k * A[j]] = min(dp[i + k * A[j]], dp[i] + k * B[j])
                k += 1
            dp[H] = min(dp[H], dp[i] + k * B[j])

    print((dp[H]))


if __name__ == '__main__':
    main()


# Optimized solution
import sys
import math  # noqa
import bisect  # noqa
import queue  # noqa


def input():
    return sys.stdin.readline().rstrip()


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

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

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


if __name__ == '__main__':
    main()
# Original solution
import time

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

INF = 10 ** 20


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

magic = []

for i in range(n):
    magic.append(list(map(int, input().split())))


que = [0]
cc = [0]
m = 0
c = 0
for i in range(h):
    if dp[i] == INF:
        continue
    for a, b in magic:
        dam = i + a
        if dp[dam] > dp[i] + b:
            dp[dam] = dp[i] + b

ans = min(dp[h:])

print(ans)

# Optimized solution
def main():
    inf = 10**9
    H, N = list(map(int, input().split()))
    AB = []
    for n in range(N):
        a, b = list(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:])))
 
 
main()
# Original solution
import time

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

INF = 10 ** 9

magic = []

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

# t = time.time()

magic.sort(reverse=True, key=lambda x: x[0])

dp = [INF] * (h + 10 ** 4)
dp[0] = 0
c = 0
for a, b in magic:
    for i in range(h):
        if dp[i] != INF:
            tmp = dp[i] + b
            c += 1
            if dp[i + a] > tmp:
                dp[i + a] = tmp

ans = min(dp[h:])

print(ans)
# print(time.time() - t)

# Optimized solution
import time

def main():
    h, n = list(map(int, input().split()))
    INF = 10 ** 9
    magic = []

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

    # t = time.time()

    magic.sort(reverse=True, key=lambda x: x[0])

    dp = [INF] * (h + 10 ** 4)
    dp[0] = 0

    for a, b in magic:
        for i in range(h):
            if dp[i] != INF:
                tmp = dp[i] + b
                if tmp < dp[i + a]:
                    dp[i + a] = tmp

    ans = min(dp[h:])

    print(ans)
    # print(time.time() - t)

main()
# Original solution
H, N = list(map(int, input().split()))
dp = [10 ** 18] * (H + 1)

dp[0] = 0

for i in range(N):
    a, b = list(map(int, input().split()))
    for j in range(H):
        nj = min(j + a, H)  # nj: 次のjのindex, 配列外参照しないようにminをとる
        dp[nj] = min(dp[nj], dp[j] + b)

print((dp[H]))



# Optimized solution
def main():
    H, N = list(map(int, input().split()))
    dp = [10 ** 18] * (H + 1)

    dp[0] = 0

    for i in range(N):
        a, b = list(map(int, input().split()))
        for j in range(H):
            nj = min(j + a, H)  # nj: 次のjのindex, 配列外参照しないようにminをとる
            dp[nj] = min(dp[nj], dp[j] + b)

    print((dp[H]))


main()
# Original solution
from heapq import heappush, heappop
min2 = lambda x,y: x if x < y else y
H,N = list(map(int,input().split()))

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

AB.sort(key=lambda x: x[1]/x[0])

cost = [(float('inf'),float('inf'))]*(H+1)
last = [0]*(H+1)

q = [((0,0), 0)]

while q:
    cli, t = heappop(q)
    if cost[t] <= cli:
        continue
    cost[t] = cli
    if t == H:
        break

    c,li = cli
    for i,(a,b) in enumerate(AB[li:], start=li):
        d = min2(H,t+a)
        if cost[d] > (c+b,i):
            heappush(q, ((c+b, i), d))

print((cost[H][0]))


# Optimized solution
min2 = lambda x,y: x if x < y else y
H,N = list(map(int,input().split()))


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

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

print((dp[-1]))
# Original solution
H, N = list(map(int, input().split()))
AB = [tuple(map(int, input().split())) for _ in range(N)]
AB.sort(key=lambda x: x[1])

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


# Optimized solution
H, N = list(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]))
# Original solution
H, N = list(map(int,input().split()))
magic = []
for i in range(N):
    a,b = list(map(int,input().split()))
    magic.append((a, b))
magic.sort(reverse=True)
amax, _ = magic[0]

INF = 1<<60

def solve():
    btab = [INF] * (H+1)
    btab[0] = 0
    for h in range(1, min(amax, H)+1):
        btab[h] = min([b for a, b in magic if a >= h])
    for h in range(2, H+1):
        for a, b in magic:
            c = b + btab[max(h-a, 0)]
            if c < btab[h]:
                btab[h] = c
    return btab[H]

print((solve()))

# Optimized solution
H, N = list(map(int,input().split()))
magic = []
for i in range(N):
    a,b = list(map(int,input().split()))
    magic.append((a, b))
magic.sort(reverse=True)
amax, _ = magic[0]

INF = 1<<60

def solve():
    btab = [INF] * (H+1)
    btab[0] = 0
    oneshot = min(amax, H)
    for h in range(1, oneshot+1):
        btab[h] = min([b for a, b in magic if a >= h])
    for h in range(2, H+1):
        for a, b in magic:
            c = b + btab[max(h-a, 0)]
            if c < btab[h]:
                btab[h] = c
    return btab[H]

print((solve()))