CodeEff/ECCO huggingface dataset:
# Original solution
import sys

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

dp = [0] * (H + 1)

for x in range(1, H + 1):
    dp[x] = min(dp[max(x - damage, 0)] + cost for damage, cost in magic)

print((dp[H]))

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

max_damage = max(damage for damage, cost in magic)
dp = [0] * (H + max_damage)

for x in range(1, H + max_damage):
    dp[x] = min(dp[x - damage] + cost for damage, cost in magic)

print((min(dp[H:])))
# Original solution
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil
    #from operator import itemgetter

    inf = 10**17
    #mod = 10**9 + 7

    h,n = list(map(int, input().split()))
    ab = [list(map(int, input().split())) for _ in range(n)]
    dp = [inf] * (3*(10**4))
    dp[0] = 0
    for i in range(3*(10**4)):
        for a,b in ab:
            if i-a >= 0:
                dp[i] = min(dp[i], dp[i-a]+b)
    res = inf
    for i in range(h, 3*(10**4)):
        res = min(res, dp[i])
    print(res)

if __name__ == '__main__':
    main()

# Optimized solution
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil
    #from operator import itemgetter

    inf = 10**17
    #mod = 10**9 + 7

    h,n = list(map(int, input().split()))
    ab = [list(map(int, input().split())) for _ in range(n)]
    dp = [inf] * (h+1)
    dp[0] = 0
    for i in range(h+1):
        for a,b in ab:
            if i+a > h:
                c = h
            else:
                c = i + a
            dp[c] = min(dp[c], dp[i]+b)

    print((dp[-1]))

if __name__ == '__main__':
    main()
# Original solution
h, n = list(map(int,input().split()))
ab = [list(map(int,input().split())) for i in range(n)]
#(a,b):=(ダメージ,消費魔力)

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

for i in range(h + 1):
    for j in range(n):
        if dp[i] == float('inf'):continue
        temp_a = i + ab[j][0] if i + ab[j][0] < h else h
        temp_b = dp[i] + ab[j][1]

        dp[temp_a] = min(dp[temp_a], temp_b)

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

# Optimized 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=[float('inf')]*(h+1)
dp[0]=0
for i in range(h):
    for j in range(n):

        next=i+a[j] if i+a[j]<=h else h
        dp[next]=min(dp[next],dp[i]+b[j])
print((dp[-1]))
# Original solution
h, n = list(map(int,input().split()))
ab = [list(map(int,input().split())) for i in range(n)]
#(a,b):=(ダメージ,消費魔力)

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

for i in range(h + 1):
    for j in range(n):
        if dp[i] == float('inf'):continue
        temp_a = i + ab[j][0] if i + ab[j][0] < h else h
        temp_b = dp[i] + ab[j][1]

        dp[temp_a] = min(dp[temp_a], temp_b)

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


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

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

        next=i+ab[j][0] if i+ab[j][0]<=h else h
        dp[next]=min(dp[next],dp[i]+ab[j][1])
print((dp[-1]))
# Original solution
hh,n = list(map(int,input().split(' ')))
spells = [list(map(int, input().split(' '))) for _ in range(n)]
h = {}
h[0] = 0

#h[health] = cost in points
for health in range(1, hh+1):
	for u,v in spells:
		h[health] = min(h[health] if health in h else +float('inf'), h[max(0,health - u)] + v)

print(h[hh])

# Optimized solution
hh,n = list(map(int,input().split(' ')))
spells = [list(map(int, input().split(' '))) for _ in range(n)]
h = [+float('inf')] * (hh+1)
h[0] = 0
for health in range(1, hh+1):
	for u,v in spells: h[health] = min(h[health], h[max(0,health - u)] + v)

print(h[hh])
# Original solution
h,n = list(map(int, input().split()))
magic = []
INF = 10**8

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

dp = [[INF for j in range(h+1)] for i in range(n+1)] #体力がjのモンスターをi番目の魔法までを使って倒せる消費魔力の最小値

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

# Optimized solution
h,n = list(map(int, input().split()))
magic = []
INF = 10**8
dp = [[INF for j in range(h+1)] for i in range(n+1)] #体力がjのモンスターをi番目の魔法までを使って倒せる消費魔力の最小値
 
for i in range(n):
    a,b = list(map(int, input().split()))
    magic.append([a, b])
 
for i in range(n):
    for j in range(h):
        if j+1 > magic[i][0]:
            dp[i+1][j+1] = min(dp[i][j+1], dp[i][j+1-magic[i][0]] + magic[i][1], dp[i+1][j+1-magic[i][0]] + magic[i][1])
        else:
            dp[i+1][j+1] = min(dp[i][j+1], magic[i][1])
            
print((dp[n][h]))
# Original solution
h,n = list(map(int, input().split()))
magic = []
INF = 10**8
dp = [[INF for j in range(h+1)] for i in range(n+1)] #体力がjのモンスターをi番目の魔法までを使って倒せる消費魔力の最小値
 
for i in range(n):
    a,b = list(map(int, input().split()))
    magic.append([a, b])
 
for i in range(n):
    for j in range(h):
        if j+1 > magic[i][0]:
            dp[i+1][j+1] = min(dp[i][j+1], dp[i][j+1-magic[i][0]] + magic[i][1], dp[i+1][j+1-magic[i][0]] + magic[i][1])
        else:
            dp[i+1][j+1] = min(dp[i][j+1], magic[i][1])
            
print((dp[n][h]))

# Optimized solution
inf = 10**15
mod = 10**9+7
h,n = list(map(int, input().split()))
ab = [list(map(int, input().split())) for i in range(n)]
dp = [[inf for j in range(h+1)] for i in range(n+1)]
for i in range(n):
    dp[i][0] = 0
    a,b = ab[i]
    for j in range(h):
        if j+1-a>=0:
            dp[i+1][j+1] = min(dp[i+1][j+1-a]+b, dp[i][j+1], dp[i][j+1-a]+b)
        else:
            dp[i+1][j+1] = min(dp[i][j+1], b)
print((dp[n][h]))
# Original solution
#!/usr/bin/env python3
import sys
import heapq
from collections import defaultdict

def solve(H: int, N: int, A: "List[int]", B: "List[int]"):
    MAX = 10**16
    minCurrent = defaultdict(lambda :MAX)
    minCurrent[0] = 0
    currentPos = [0]
    heapq.heapify(currentPos)
    visited = set()
    while len(currentPos) > 0:
        cp = heapq.heappop(currentPos)
        if cp in visited:
            continue
        if cp > H:
            break
        visited.add(cp)
        cc = minCurrent[cp]
        for i in range(N):
            heapq.heappush(currentPos, cp + A[i])
            minCurrent[cp + A[i]] = min(minCurrent[cp + A[i]],cc+B[i])
    c = MAX
    for key in minCurrent:
        if key >=H:
            c = min(c,minCurrent[key])
    print(c)
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    H = int(next(tokens))  # type: int
    N = int(next(tokens))  # type: int
    A = [int()] * (N)  # type: "List[int]"
    B = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
    solve(H, N, A, B)

if __name__ == '__main__':
    main()


# Optimized solution
#!/usr/bin/env python3
import sys
import heapq


def solve(H: int, N: int, A: "List[int]", B: "List[int]"):
    dp = [10**16]*(H+1)
    dp[0] = 0
    positions = [0]
    for i in range(len(dp)):
        c = dp[i]
        for j in range(N):
            ni = min(H, i+A[j])
            dp[ni] = min(dp[ni], c+B[j])
    print((dp[-1]))
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    H = int(next(tokens))  # type: int
    N = int(next(tokens))  # type: int
    A = [int()] * (N)  # type: "List[int]"
    B = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
    solve(H, N, A, B)


if __name__ == '__main__':
    main()
# Original solution
H, N = list(map(int, input().split()))

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

DP = [0] + [10**9]*H

for h in range(H):
  if DP[h] == 10**9:
    continue
  for damage, mp in magic:
    DP[min(h + damage, H)] = min(DP[min(h + damage, H)], DP[h] + mp)
print((DP[H]))

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

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

DP = [0] * (H+10**4)

for h in range(1, H+1):
  DP[h] = min(DP[h - damage] + mp for damage, mp in magic)
print((DP[H]))
# Original solution
import sys

import re
import math
import collections
import decimal
import bisect
import itertools
import fractions
import functools
import copy
import heapq
import decimal
import statistics
import queue

sys.setrecursionlimit(10000001)
INF = 10 ** 10
MOD = 10 ** 9 + 7

ni = lambda: int(sys.stdin.readline())
ns = lambda: list(map(int, sys.stdin.readline().split()))
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===


def main():
    h, n = ns()
    d = [na() for _ in range(n)]

    mat = [INF for _ in range(h + 1)]

    mat[0] = 0
    for i in range(h):
        if mat[i] == INF:
            continue
        for a, b in d:
            if i + a < h + 1:
                mat[i + a] = min(mat[i + a], mat[i] + b)
            else:
                mat[h] = min(mat[h], mat[i] + b)

    print((mat[h]))


if __name__ == '__main__':
    main()


# Optimized solution
import sys

# import re
# import math
# import collections
# import decimal
# import bisect
# import itertools
# import fractions
# import functools
# import copy
# import heapq
# import decimal
# import statistics
# import queue

sys.setrecursionlimit(10000001)
INF = 10 ** 10
MOD = 10 ** 9 + 7

ni = lambda: int(sys.stdin.readline())
ns = lambda: list(map(int, sys.stdin.readline().split()))
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===


def main():
    h, n = ns()
    d = [na() for _ in range(n)]

    mat = [INF for _ in range(h + 1)]

    mat[0] = 0
    for i in range(h):
        if mat[i] == INF:
            continue
        for a, b in d:
            if i + a < h + 1:
                mat[i + a] = min(mat[i + a], mat[i] + b)
            else:
                mat[h] = min(mat[h], mat[i] + b)

    print((mat[h]))


if __name__ == '__main__':
    main()
# Original solution
MAX_LIMIT = 1e30
H, N = list(map(int, input().split()))
A, B = [], []
for _ in range(N):
    a, b = list(map(int, input().split()))
    A.append(a)  # HP
    B.append(b)  # power

# dp[i] means minimum power used to reduce HP i
dp = [MAX_LIMIT] * (H + max(A))
dp[0] = 0

for i in range(1, H + max(A)):
    cands = []
    for a, b in zip(A, B):
        if i - a >= 0:
            cands.append(b + dp[i - a])
    if len(cands) == 0:
        dp[i] = MAX_LIMIT  # we cannot directly reach this point
    else:
        dp[i] = min(cands)

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


# Optimized solution
h, n = list(map(int, input().split()))
ab = [list(map(int, input().split())) for _ in range(n)]
dp =[0]*(h+max(a for a,b in ab))
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)]

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

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

ans = dp[n][h]
print(ans)


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

dp = [[float("inf")] * (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(1, h + 1):
        a, b = ab[i-1]
        dp[i][j] = min(dp[i-1][j], dp[i][max(j-a, 0)] + b)

ans = dp[n][h]
print(ans)
# Original solution
h, n = list(map(int, input().split()))
ab = [list(map(int, input().split())) for _ in range(n)]

dp = [[float("inf")] * (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(1, h + 1):
        a, b = ab[i-1]
        dp[i][j] = min(dp[i-1][j], dp[i][max(j-a, 0)] + b)

ans = dp[n][h]
print(ans)


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

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

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

ans = dp[n][h]
print(ans)
# Original solution
h,n=list(map(int,input().split()))
AB=[list(map(int,input().split())) for i in range(n)]

A_max=max(AB)[0]
DP=[0]+[float("inf")]*(h+A_max)
for i in range(h):
    if DP[i]==float("inf"):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
from sys import stdin
readline=stdin.readline
h,n=list(map(int,readline().split()))
AB=[list(map(int,readline().split())) for i in range(n)]

A_max=max(AB)[0]
DP=[0]+[float("inf")]*(h+A_max)
for i in range(h):
    if DP[i]==float("inf"):continue
    for a,b in AB:
        t=DP[i]+b
        if t<DP[i+a]:
            DP[i+a]=t
print((min(DP[h:])))
# Original solution
h,n=(int(i) for i in input().split())
l=[]
for i in range(n):
  a,b=(int(i) for i in input().split())
  l.append([a,b])
pocket=[0]
for i in range(h):
  r=[]
  for j in range(n):
    a=l[j][0]
    b=l[j][1]
    r.append(pocket[max(0,i+1-a)]+b)
  pocket.append(min(r))
print((pocket[h]))


# Optimized solution
h,n=(int(i) for i in input().split())
l=[]
for i in range(n):
  a,b=(int(i) for i in input().split())
  l.append([a,b])
pocket=[0]
for i in range(h):
  mini=pocket[max(0,i+1-l[0][0])]+l[0][1]
  for j in range(n-1):
    a=l[j+1][0]
    b=l[j+1][1]
    if pocket[max(0,i+1-a)]+b<mini:
      mini=pocket[max(0,i+1-a)]+b
  pocket.append(mini)
print((pocket[h]))
# Original solution

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

max_a = max(a for a,b in ab_list)
W = H + 1 + max_a
dp = [0] * W

for i in range(W):
    dp[i] = 10**9
    for a,b in ab_list:
        dp[i] = min(dp[i], dp[i-a]+b)

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

# Optimized solution

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

max_a = max(a for a,b in ab_list)
W = H + 1 + max_a
dp = [0] * W

for i in range(W):
    dp[i] = min(dp[i-a]+b for a,b in ab_list)

print((min(dp[H-1:])))
# Original solution
import sys
import math

def main():
    h_and_n_s = sys.stdin.readline().strip().split(' ')
    h, n = [int(s) for s in h_and_n_s]
    a = [-1] * n
    b = [-1] * n

    for i in range(n):
        a[i], b[i] = [int(s) for s in sys.stdin.readline().strip().split(' ')]

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

    for point in range(h+1):
        for i in range(n):
            if point <= a[i]:
                dp[point] = min(dp[point], b[i])
                continue

            dp[point] = min(dp[point], dp[point-a[i]] + b[i])

    print((dp[h]))


if __name__ == '__main__':
    main()


# Optimized solution
import sys

def main():
    h_and_n_s = sys.stdin.readline().strip().split(' ')
    h, n = [int(s) for s in h_and_n_s]
    a = [-1] * n
    b = [-1] * n

    # max_a = 0
    # ef_i = -1
    for i in range(n):
        a[i], b[i] = [int(s) for s in sys.stdin.readline().strip().split(' ')]
        # max_a = max(max_a, a[i])
        # if a[ef_i] / b[ef_i] < a[i] / b[i]:
        #     ef_i = i

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

    for point in range(h+1):
        for i in range(n):
            if point <= a[i]:
                dp[point] = min(dp[point], b[i])
                continue

            dp[point] = min(dp[point], dp[point-a[i]] + b[i])

    print((dp[h]))


if __name__ == '__main__':
    main()
# Original solution
H,N = list(map(int,input().split()))
AB = [list(map(int,input().split())) for _ in range(N)]
dp = [[10**18]*(N+1) for _ in range(H+1)]
dp[0][0] = 0
for h in range(H+1):
    for i in range(N):
        dp[h][i+1] = min(dp[h][i], dp[max(0,h-AB[i][0])][i+1] + AB[i][1])
print((dp[H][N]))

# Optimized solution
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:])))
# Original solution
import sys

INF = float("inf")


def main():
    input = sys.stdin.readline
    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 = [INF] * (H + max(A))
    dp[0] = 0
    for h in range(H):
        for a, b in zip(A, B):
            dp[h+a] = min(dp[h+a], dp[h]+b)
    ans = min(dp[H:])
    print(ans)


if __name__ == "__main__":
    main()


# Optimized solution
import sys

input = sys.stdin.readline

INF = float("inf")


def main():
    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 = [INF] * (H + max(A))
    dp[0] = 0
    for h in range(H):
        for a, b in zip(A, B):
            if dp[h]+b < dp[h+a]:
                dp[h+a] = dp[h]+b
    ans = min(dp[H:])
    print(ans)


if __name__ == "__main__":
    main()
# Original solution
H,N = list(map(int,input().split()))
dp = [[[0,float('INF')]for i in range(H+1)] for _ in range(N+1)]
#↑[ダメージ、MP]

for i in range(N+1):
    dp[i][0][1]=0

# dp[i][j] -> iまでの魔法が使えるとき、j以上のダメージを与えるための最小限のMP
for i in range(1,N+1):
    a,b = list(map(int,input().split()))
    for j in range(1,H+1):
        """
        その魔法を使わない場合のdp[i][j]
        dp[i-1][j]とdp[i][j-1]のうち、MPが若いものを使う。
        ただし、dp[i][j-1]に関しては、ダメージ(dp[i][j-1][0])がj未満の場合、使わない
        """
        dp[i][j] = dp[i-1][j][:]
        if dp[i][j-1][0] >= j and dp[i][j-1][1] < dp[i][j][1]:
            dp[i][j] = dp[i][j-1][:]
        
        """
        その魔法を使う場合のdp[i][j]
        j-a<=0の場合、dp[i][j]は
        dp[i][j]と[a,b]のうち、MPが若いものを使う。
        j-a>0の場合は、
        dp[i][j]とdp[i][j-a][1]+b,dp[i-1][j-a][1]+bのうち、MPが若いものを使う。
        """
        if j-a<=0:
            if b < dp[i][j][1]:
                dp[i][j]=[a,b]

        else:
            if dp[i][j-a][1]+b <= dp[i][j][1] and dp[i][j-a][1]+b <= dp[i-1][j-a][1]+b:
                dp[i][j]=[dp[i][j-a][0]+a,dp[i][j-a][1]+b]
            elif dp[i-1][j-a][1]+b <= dp[i][j][1] and dp[i-1][j-a][1]+b <= dp[i][j-a][1]+b:
                dp[i][j]=[dp[i-1][j-a][0]+a,dp[i-1][j-a][1]+b]


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

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

dp = [float("INF")]*(H+1)
dp[0] = 0
for i in range(N):
    a,b= list(map(int,input().split()))
    for j in range(1,H+1):
        dp[j] = min(dp[j],dp[max((j-a),0)]+b)

print((dp[-1]))
# Original solution
h,n = list(map(int, input().split()))
ab = []
amax = 10**5
for _ in range(n):
  ab.append(tuple(map(int,input().split())))
  amax = max(amax,ab[-1][1])
p = [10**10]*(h+amax+1)
q = [(i,j) for i,j in ab]
while q:
  a,b = q.pop()
  if b<p[a]: p[a]=b
  else: b=p[a]
  if a>=h: continue
  for i,j in ab:
    if b+j<p[a+i]:
      p[a+i]=b+j
      q.append((a+i,b+j))
print((min(p[h:])))

# Optimized solution
h,n = list(map(int, input().split()))
ab = []
amax = 10**5
for _ in range(n):
  ab.append(tuple(map(int,input().split())))
amax = max(a for a,b in ab)
p = [0]*(h+amax+1)
for i in range(1,h+amax):
  p[i] = min(p[i-a]+b for a,b in ab)
print((p[h]))
# Original solution
#E re
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 = [float('inf')] * (H+1)
DP[0] = 0

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

print((int(DP[H])))


# Optimized solution
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

for i in range(H):
    minM = float('inf')
    for j in range(N):
        if i+1 - A[j] >= 0:
            M = DP[i-A[j]] + B[j]
        else:
            M = B[j]
        if minM > M:
            minM = M
    DP[i] = minM

print((int(DP[H-1])))
# Original solution
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()))

INF=10**9
dp=[INF]*(H+1)
# dp[x]:xダメージを与えるための最小魔力
dp[0]=0
for i in range(N):
  for j in range(len(dp)):
    if dp[j]!=INF:
      if j+A[i]<len(dp):
        if dp[j+A[i]]>dp[j]+B[i]:
          dp[j+A[i]]=dp[j]+B[i]
      else:
        if dp[len(dp)-1]>dp[j]+B[i]:
          dp[len(dp)-1]=dp[j]+B[i]
print((dp[-1]))

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

INF=10**9
dp=[INF]*(H+max(A))
# dp[x]:xダメージを与えるための最小魔力
dp[0]=0
for i in range(N):
  for j in range(H):
    if dp[j]!=INF:
      if dp[j+A[i]]>dp[j]+B[i]:
        dp[j+A[i]]=dp[j]+B[i]
print((min(dp[H:])))
# Original solution
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return eval(input())

def main():
  h,n=LI()
  w=[]
  v=[]
  for _ in range(n):
    _w,_v=LI()
    w.append(_w)
    v.append(_v)

  dp=[[inf]*(h+10**4+1) for _ in range(n+1)]
  dp[0][0]=0
  for i in range(n):
    for j in range(h+10**4):
      if j<w[i]:
        dp[i+1][j]=dp[i][j]
      else:
        dp[i+1][j]=min(dp[i][j],dp[i+1][j-w[i]]+v[i])
  ans=inf
  for i in range(n+1):
    for j in range(h,h+10**4):
      ans=min(ans,dp[i][j])

  return ans

# main()
print((main()))


# Optimized solution
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return eval(input())

def main():
  h,n=LI()
  w=[]
  v=[]
  max_w=0
  for _ in range(n):
    _w,_v=LI()
    w.append(_w)
    v.append(_v)
    max_w=max(max_w,_w)

  dp=[[inf]*(h+10**4+1) for _ in range(n+1)]
  dp[0][0]=0
  for i in range(n):
    for j in range(h+max_w):
      if j<w[i]:
        dp[i+1][j]=dp[i][j]
      else:
        dp[i+1][j]=min(dp[i][j],dp[i+1][j-w[i]]+v[i])
  ans=inf
  for i in range(n+1):
    for j in range(h,h+max_w):
      ans=min(ans,dp[i][j])

  return ans

# main()
print((main()))