import sys, re

from collections import deque, defaultdict, Counter

from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees#, log2

from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby

from operator import itemgetter, mul

from copy import deepcopy

from string import ascii_lowercase, ascii_uppercase, digits

from bisect import bisect, bisect_left, insort, insort_left

from fractions import gcd

from heapq import heappush, heappop

from functools import reduce

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

def INT(): return int(eval(input()))

def MAP(): return list(map(int, input().split()))

def LIST(): return list(map(int, input().split()))

def ZIP(n): return list(zip(*(MAP() for _ in range(n))))

sys.setrecursionlimit(10 ** 9)

INF = float('inf')

mod = 10**9 + 7



def main():

	H, N = MAP()

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

	for i in range(N):

		A[i], B[i] = MAP()



	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 < A[i]:

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

			if j>= A[i]:

				dp[i+1][j] = min(dp[i][j], dp[i+1][j-A[i]]+B[i])

			



	#for i in range(N+1):

	#	print(dp[i])



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



if __name__ == '__main__':

	main()







import sys, re

from collections import deque, defaultdict, Counter

from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees#, log2

from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby

from operator import itemgetter, mul

from copy import deepcopy

from string import ascii_lowercase, ascii_uppercase, digits

from bisect import bisect, bisect_left, insort, insort_left

from fractions import gcd

from heapq import heappush, heappop

from functools import reduce

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

def INT(): return int(eval(input()))

def MAP(): return list(map(int, input().split()))

def LIST(): return list(map(int, input().split()))

def ZIP(n): return list(zip(*(MAP() for _ in range(n))))

sys.setrecursionlimit(10 ** 9)

INF = float('inf')

mod = 10**9 + 7



def main():

	H, N = MAP()

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

	for i in range(N):

		A[i], B[i] = MAP()



	dp = [INF]*(H+1)

	dp[0] = 0





	for i in range(N):

		for j in range(H+1):

			if j < A[i]:

				dp[j] = min(dp[j], B[i])

			if j>= A[i]:

				dp[j] = min(dp[j], dp[j-A[i]]+B[i])



	print((dp[H]))



if __name__ == '__main__':

	main()







import sys, re
from collections import deque, defaultdict, Counter
from math import (
    ceil,
    sqrt,
    hypot,
    factorial,
    pi,
    sin,
    cos,
    tan,
    asin,
    acos,
    atan,
    radians,
    degrees,
)  # , log2
from itertools import (
    accumulate,
    permutations,
    combinations,
    combinations_with_replacement,
    product,
    groupby,
)
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce


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


def INT():
    return int(eval(input()))


def MAP():
    return list(map(int, input().split()))


def LIST():
    return list(map(int, input().split()))


def ZIP(n):
    return list(zip(*(MAP() for _ in range(n))))


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


def main():
    H, N = MAP()
    A, B = [0] * N, [0] * N
    for i in range(N):
        A[i], B[i] = MAP()
    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 < A[i]:
                dp[i + 1][j] = min(dp[i][j], B[i])
            if j >= A[i]:
                dp[i + 1][j] = min(dp[i][j], dp[i + 1][j - A[i]] + B[i])
    # for i in range(N+1):
    # 	print(dp[i])
    print((dp[N][H]))


if __name__ == "__main__":
    main()

import sys, re
from collections import deque, defaultdict, Counter
from math import (
    ceil,
    sqrt,
    hypot,
    factorial,
    pi,
    sin,
    cos,
    tan,
    asin,
    acos,
    atan,
    radians,
    degrees,
)  # , log2
from itertools import (
    accumulate,
    permutations,
    combinations,
    combinations_with_replacement,
    product,
    groupby,
)
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce


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


def INT():
    return int(eval(input()))


def MAP():
    return list(map(int, input().split()))


def LIST():
    return list(map(int, input().split()))


def ZIP(n):
    return list(zip(*(MAP() for _ in range(n))))


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


def main():
    H, N = MAP()
    A, B = [0] * N, [0] * N
    for i in range(N):
        A[i], B[i] = MAP()
    dp = [INF] * (H + 1)
    dp[0] = 0
    for i in range(N):
        for j in range(H + 1):
            if j < A[i]:
                dp[j] = min(dp[j], B[i])
            if j >= A[i]:
                dp[j] = min(dp[j], dp[j - A[i]] + B[i])
    print((dp[H]))


if __name__ == "__main__":
    main()

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