from collections import Counter,defaultdict,deque

from heapq import heappop,heappush,heapify

import sys,bisect,math,itertools,pprint,fractions

sys.setrecursionlimit(10**8)

mod = 10**9+7

mod2 = 998244353

INF = float('inf')

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

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

def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))



h,n = inpl()

att = []

cost = []

for i in range(n):

    a,b = inpl()

    att.append(a); cost.append(b)

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

dp[0][0] = 0



for i in range(n):

    cnt = h//att[i]

    for j in range(h+1):

        if att[i] >= j:

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

            continue

        dp[i+1][j] = min(dp[i][j], cost[i]+dp[i+1][j-att[i]])

# pprint.pprint(dp)

print((dp[n][h]))
from collections import Counter,defaultdict,deque

from heapq import heappop,heappush,heapify

import sys,bisect,math,itertools,fractions,pprint

sys.setrecursionlimit(10**8)

mod = 10**9+7

INF = float('inf')

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

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



W,n = inpl()

wv = [inpl() for _ in range(n)]

dp = [INF] * (W+1)

dp[0] = 0

for i in range(n):

    w,v = wv[i]

    for j in range(W+1):

        if j < w:

            dp[j] = min(dp[j], v)

            continue

        dp[j] = min(dp[j], dp[j-w] + v)

print((dp[W]))
from collections import Counter, defaultdict, deque
from heapq import heappop, heappush, heapify
import sys, bisect, math, itertools, pprint, fractions

sys.setrecursionlimit(10**8)
mod = 10**9 + 7
mod2 = 998244353
INF = float("inf")


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


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


def inpln(n):
    return list(int(sys.stdin.readline()) for i in range(n))


h, n = inpl()
att = []
cost = []
for i in range(n):
    a, b = inpl()
    att.append(a)
    cost.append(b)
dp = [[INF for i in range(h + 1)] for j in range(n + 1)]
dp[0][0] = 0
for i in range(n):
    cnt = h // att[i]
    for j in range(h + 1):
        if att[i] >= j:
            dp[i + 1][j] = min(dp[i][j], cost[i])
            continue
        dp[i + 1][j] = min(dp[i][j], cost[i] + dp[i + 1][j - att[i]])
# pprint.pprint(dp)
print((dp[n][h]))

from collections import Counter, defaultdict, deque
from heapq import heappop, heappush, heapify
import sys, bisect, math, itertools, fractions, pprint

sys.setrecursionlimit(10**8)
mod = 10**9 + 7
INF = float("inf")


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


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


W, n = inpl()
wv = [inpl() for _ in range(n)]
dp = [INF] * (W + 1)
dp[0] = 0
for i in range(n):
    w, v = wv[i]
    for j in range(W + 1):
        if j < w:
            dp[j] = min(dp[j], v)
            continue
        dp[j] = min(dp[j], dp[j - w] + v)
print((dp[W]))

-import sys, bisect, math, itertools, pprint, fractions +import sys, bisect, math, itertools, fractions, pprint -mod2 = 998244353 -def inpln(n): -    return list(int(sys.stdin.readline()) for i in range(n)) - - -h, n = inpl() -att = [] -cost = [] +W, n = inpl() +wv = [inpl() for _ in range(n)] +dp = [INF] * (W + 1) +dp[0] = 0 -    a, b = inpl() -    att.append(a) -    cost.append(b) -dp = [[INF for i in range(h + 1)] for j in range(n + 1)] -dp[0][0] = 0 -for i in range(n): -    cnt = h // att[i] -    for j in range(h + 1): -        if att[i] >= j: -            dp[i + 1][j] = min(dp[i][j], cost[i]) +    w, v = wv[i] +    for j in range(W + 1): +        if j < w: +            dp[j] = min(dp[j], v) -        dp[i + 1][j] = min(dp[i][j], cost[i] + dp[i + 1][j - att[i]]) -# pprint.pprint(dp) -print((dp[n][h])) +        dp[j] = min(dp[j], dp[j - w] + v) +print((dp[W]))