CodeEff/ECCO huggingface dataset:
# Original solution
#H = int(input())
H,N = list(map(int,input().split()))
#H = sorted(list(map(int,input().split())))
AB = [list(map(int,input().split())) for i in range(N)]
dp = [[float('inf') for i in range(H)] for j in range(N)]
for i in range(N):
    dp[i][0] = 0
for j in range(H):
    if j-AB[0][0] >= 0:
        dp[0][j] = dp[0][j-AB[0][0]]+AB[0][1]
for i in range(1,N):
    for j in range(H):
        if j-AB[i-1][0] >= 0:
            dp[i][j] = min(dp[i-1][j],dp[i-1][j-AB[i-1][0]]+AB[i-1][1])
        if j-AB[i][0] >= 0:
            dp[i][j] = min(dp[i-1][j],dp[i][j-AB[i][0]]+AB[i][1])

ans = float('inf')
for i in range(N):
    for j in range(max(0,H-AB[i][0]),H):
        if dp[-1][j] != float('inf') and j+AB[i][0] >= H:
            ans = min(ans,dp[-1][j]+AB[i][1])
print(ans)

# Optimized solution
#H = int(input())
H,N = list(map(int,input().split()))
#H = sorted(list(map(int,input().split())))
AB = sorted([list(map(int,input().split())) for i in range(N)])
dp = [float('inf') for i in range(H)]
dp[0] = 0
for i in range(N):
    for j in range(H):
        if j-AB[i][0] >= 0:
            dp[j] = min(dp[j],dp[j-AB[i][0]]+AB[i][1])
ans = float('inf')
for i in range(N):
    for j in range(max(0,H-AB[i][0]),H):
        if dp[j] != float('inf') and j+AB[i][0] >= H:
            ans = min(ans,dp[j]+AB[i][1])
print(ans)
# 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配列を作成
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は100000000 + 消費魔力
        t = dp[i] + b
        # dp[i + a] aはダメージ量
        if t < dp[i + a]:
            dp[i + a] = t

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
H, N  = list(map(int, input().split()))
# hitpoint H
# waza N
As = [] # damage
Bs = [] # MP comsumptions
for i in range(N):
    a,b = list(map(int, input().split()))
    As.append(a)
    Bs.append(b)

"""
dp[i][j] = i番目までの魔法を見たとき、ダメージがちょうどjになる最小値
"""
INF = 10**10
M = 21000
dp = [[INF]*M for i in range(N+1)]
dp[0][0] = 0
for i,(a,b) in enumerate(zip(As,Bs)):
    dp[i+1][:] = dp[i][:]
    for j in range(H):        
        dp[i+1][j+a] = min(dp[i][j+a], dp[i+1][j]+b)
        # print(i,j,"ab",a,b,"dp",dp[i][j],dp[i][j+1],dp[i][j]+b)
print((min(dp[N][H:])))


# Optimized solution
H, N  = list(map(int, input().split()))
# hitpoint H
# waza N
As = [] # damage
Bs = [] # MP comsumptions
for i in range(N):
    a,b = list(map(int, input().split()))
    As.append(a)
    Bs.append(b)

INF = 10**10
M = 21000
dp = [INF]*M
dp[0] = 0
for i,(a,b) in enumerate(zip(As,Bs)):
    # update
    for j in range(H):
        # 何回でも使っていい⇛dp[i+1][j]+b
        dp[j+a] = min(dp[j+a], dp[j]+b) 
print((min(dp[H:])))
# Original solution
H, N = list(map(int, input().split()))
da, cost = [0] * N, [0] * N
for i in range(N):
    da[i],cost[i]=list(map(int, input().split()))

max_da=max(da)*10  
dp = [float("inf") for i in range(H+max_da)]
dp[0]=0

for j in range(N):
    for i in range(H+max_da):
        if i-da[j]>=0:
            dp[i]=min(dp[i],dp[i-da[j]]+cost[j])

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

# Optimized solution
H, N = list(map(int, input().split()))
da, cost = [0] * N, [0] * N
for i in range(N):
    da[i],cost[i]=list(map(int, input().split()))

max_da=max(da) 
dp = [float("inf") for i in range(H+max_da)]
dp[0]=0

for i in range(H+max_da):
    for j in range(N):
        if i-da[j]>=0:
            dp[i]=min(dp[i],dp[i-da[j]]+cost[j])

print((min(dp[H:])))
# Original solution
#n=int(input())
h,n=list(map(int,input().split()))
#a=list(map(int,input().split()))
l=[list(map(int,input().split())) for i in range(n)]
#l=[list(input().split()) for i in range(n)]

amax=0
for i in range(n):
    if amax<l[i][0]:
        amax=l[i][0]
        
ldp=[[0 for j in range(h+amax)]for i in range(n)]
for i in range(n):
    for j in range(h+amax):
        if i==0:
            ldp[i][j]=-(-(j+1)//l[i][0])*l[i][1]
        else:
            if j>=l[i][0]:
                ldp[i][j]=min(ldp[i-1][j],ldp[i][j-l[i][0]]+l[i][1])
            else:
                ldp[i][j]=min(ldp[i-1][j],l[i][1])
print((min(ldp[-1][h-1:])))

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


        
ldp=[[0 for j in range(h)]for i in range(n)]
for i in range(n):
    for j in range(h):
        if i==0:
            ldp[i][j]=-(-(j+1)//l[i][0])*l[i][1]
        else:
            if j>=l[i][0]:
                ldp[i][j]=min(ldp[i-1][j],ldp[i][j-l[i][0]]+l[i][1])
            else:
                ldp[i][j]=min(ldp[i-1][j],l[i][1])
print((ldp[-1][-1]))
# 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=float("inf")
dp=[inf]*(h+1)
 
dp[0]=0

for a,b in AB:
    for i in range(h):
        if dp[i]!=float("inf"):
            dp[min(i+a,h)]=min(dp[min(i+a,h)],dp[i]+b)
print((dp[-1]))
            

# 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)
 
Ama = max(A)
 
dp=[float("inf")]*(h+Ama+1)
dp[0]=0
 
for i in range(h+1):
    for j in range(n):
        dp[i+A[j]]=min(dp[i+A[j]],dp[i]+B[j])
print((min(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)
 
Ama = max(A)
 
dp=[float("inf")]*(h+Ama+1)
dp[0]=0
 
for i in range(h+1):
    for j in range(n):
        dp[i+A[j]]=min(dp[i+A[j]],dp[i]+B[j])
print((min(dp[h:])))

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

h,n=list(map(int,input().split()))
A=[]
AB=[]
for i in range(n):
    a,b=list(map(int,input().split()))
    A.append(a)
    AB.append((a,b))
    
maA=max(A)
dp=[float("inf")]*(h+maA+1)
dp[0]=0

for i in range(h+1):
    for a,b in AB:
        dp[i+a]=min(dp[i+a],dp[i]+b)
print((min(dp[h:])))
# Original solution
h,n=list(map(int,input().split()))
AB=[]
maA=0
inf=float("inf")
for i in range(n):
   a,b=list(map(int,input().split()))
   maA=max(maA,a)
   AB.append((a,b))

dp=[inf]*(h+maA+1)
dp[0]=0
for i in range(h+1):
   for aj,bj in AB:
      dp[i+aj]=min(dp[i+aj],dp[i]+bj)
print((min(dp[h:])))

# Optimized solution
h,n=list(map(int,input().split()))
L=[]
maA=0
inf=float("inf")
for i in range(n):
      a,b=list(map(int,input().split()))
      L.append((a,b))
      maA=max(maA,a)

dp=[inf]*(h+maA+1)
dp[0]=0
for i in range(h):
      for j in L:
            dp[i+j[0]]=min(dp[i+j[0]],dp[i]+j[1])
      
print((min(dp[h:])))
# Original solution
# coding: utf-8
H, N = list(map(int, input().split()))
L = []
for i in range(N):
    L.append(list(map(int, input().split())))
dp = [float("inf") for _ in range(H+1)] 
dp[0] = 0
for i in range(1, H+1):
    for j in range(N):
        a, b = L[j]
        if i <= a:
            dp[i] = min(dp[i], b)
        else:
            dp[i] = min(dp[i], dp[i-a] + b)
    # print(*dp)
print((dp[H]))

# Optimized solution
# coding: utf-8
H, N = list(map(int, input().split()))
L = []
for i in range(N):
    L.append(list(map(int, input().split())))
dp = [float("inf") for _ in range(H+1)] 
dp[0] = 0
top = 10**9
for i in range(1, H+1):
    for j in range(N):
        a, b = L[j]
        if i <= a:
            dp[i] = min(dp[i], b)
        else:
            dp[i] = min(dp[i], dp[i-a] + b)
    # print(*dp)
print((dp[H]))
# Original solution

def resolve():
    INF = 1<<60
    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 = [[INF]*(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__":
    resolve()


# Optimized solution

def resolve():
    INF = 1<<60
    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 = [[INF]*(H+1) for _ in range(N+1)]
    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(dp[i][j], B[i])
            else:
                dp[i + 1][j] = min(dp[i][j], dp[i + 1][j - A[i]] + B[i])

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


if __name__ == "__main__":
    resolve()
# Original solution
h,n = list(map(int, input().split()))
ab = []
a = []
b = []
for _ in range(n):
    t_ab = list(map(int, input().split()))
    ab.append(t_ab)
    a.append(t_ab[0])
    b.append(t_ab[1])

maxa = max(a)
hmaxa = h+maxa
dp = [float("inf") for _ in range(hmaxa)]
dp[0] = 0

for i in range(hmaxa):
    ab_child = [dp[i]]
    for j in ab:
        if j[0] <= i:
            ab_child.append(dp[i-j[0]] + j[1])
        dp[i] = min(min(ab_child), dp[i])

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

# Optimized solution
h,n = list(map(int, input().split()))
ab = []
a = []
b = []
for _ in range(n):
    t_ab = list(map(int, input().split()))
    ab.append(t_ab)
    a.append(t_ab[0])
    b.append(t_ab[1])

maxa = max(a)
hmaxa = h+maxa
dp = [0 for _ in range(hmaxa)]

for i in range(1, hmaxa):
    ab_child = [dp[i-a]+b for a,b in ab]
    dp[i] = min(ab_child)

print((min(dp[h:])))
# Original solution
# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(eval(input()))
def MAP(): return list(map(int, input().split()))
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

H, N = MAP()
AB = [()]
for i in range(N):
    a, b = MAP()
    AB.append((a, b))

dp = list2d(N+1, 20007, INF)
dp[0][0] = 0
for i in range(1, N+1):
    a, b = AB[i]
    for j in range(20007):
        dp[i][j] = min(dp[i][j], dp[i-1][j])
        if j-a >= 0:
            dp[i][j] = min(dp[i][j], dp[i-1][j-a] + b)
            dp[i][j] = min(dp[i][j], dp[i][j-a] + b)
print((min(dp[N][H:])))


# Optimized solution
# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(eval(input()))
def MAP(): return list(map(int, input().split()))
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

H, N = MAP()
AB = [()]
for i in range(N):
    a, b = MAP()
    AB.append((a, b))

dp = list2d(N+1, 20007, INF)
dp[0][0] = 0
for i in range(1, N+1):
    a, b = AB[i]
    for j in range(20007):
        dp[i][j] = min(dp[i][j], dp[i-1][j])
        if j-a >= 0:
            dp[i][j] = min(dp[i][j], dp[i][j-a] + b, dp[i-1][j-a] + b)
print((min(dp[N][H:])))
# Original solution
# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(eval(input()))
def MAP(): return list(map(int, input().split()))
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

H, N = MAP()
AB = [()]
for i in range(N):
    a, b = MAP()
    AB.append((a, b))

dp = list2d(N+1, 20007, INF)
dp[0][0] = 0
for i in range(1, N+1):
    a, b = AB[i]
    for j in range(20007):
        dp[i][j] = min(dp[i][j], dp[i-1][j])
        if j-a >= 0:
            dp[i][j] = min(dp[i][j], dp[i][j-a] + b, dp[i-1][j-a] + b)
print((min(dp[N][H:])))


# Optimized solution
# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(eval(input()))
def MAP(): return list(map(int, input().split()))
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

H, N = MAP()
AB = []
for i in range(N):
    a, b = MAP()
    AB.append((a, b))

dp = [INF] * 20007
dp[0] = 0
for i in range(20007):
    for a, b in AB:
        if i-a >= 0:
            dp[i] = min(dp[i], dp[i-a] + b)
ans = min(dp[H:])
print(ans)
# Original solution
# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(eval(input()))
def MAP(): return list(map(int, input().split()))
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

H, N = MAP()
AB = []
for i in range(N):
    a, b = MAP()
    AB.append((a, b))

dp = [INF] * 20007
dp[0] = 0
for i in range(20007):
    for a, b in AB:
        if i-a >= 0:
            dp[i] = min(dp[i], dp[i-a] + b)
ans = min(dp[H:])
print(ans)


# Optimized solution
# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(eval(input()))
def MAP(): return list(map(int, input().split()))
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

H, N = MAP()
AB = []
for i in range(N):
    a, b = MAP()
    AB.append((a, b))

dp = [INF] * 20007
dp[0] = 0
for a, b in AB:
    for i in range(20007):
        if i-a >= 0:
            dp[i] = min(dp[i], dp[i-a] + b)
ans = min(dp[H:])
print(ans)
# Original solution
def solve():
    H,N = list(map(int, input().split()))
    # Aが消費HP, Bが消費MP
    ABs = [list(map(int, input().split())) for _ in range(N)]
    dp_table = [[0]*(H+1) for _ in range(N+1)]
    # dp_table[i][j] : i番目の魔法から消化HPがj以上となる、MPの最小値
    for j in range(1,H+1): dp_table[0][j] = 10**9
    for i in range(N):
        for j in range(H+1):
            if j-ABs[i][0]<0:
                dp_table[i+1][j] = min(dp_table[i][j], ABs[i][1])
            else:
                dp_table[i+1][j] = min(dp_table[i][j], dp_table[i+1][j-ABs[i][0]]+ABs[i][1])
                
    print((dp_table[N][H]))
    
solve()

# Optimized solution
def solve():
    H,N = list(map(int, input().split()))
    # Aが消費HP, Bが消費MP
    ABs = [list(map(int, input().split())) for _ in range(N)]
    # dp_table = [[10**9]*(H+1)]+[[0]*(H+1) for _ in range(N)]
    dp_table = [[0]*(H+1) for _ in range(N+1)]
    # dp_table[i][j] : i番目の魔法から消化HPがj以上となる、MPの最小値
    for j in range(1,H+1): dp_table[0][j] = 10**9
    # print(dp_table)
    for i in range(N):
        for j in range(H+1):
            if j-ABs[i][0]<0:
                dp_table[i+1][j] = min(dp_table[i][j], ABs[i][1])
            else:
                dp_table[i+1][j] = min(dp_table[i][j], dp_table[i+1][j-ABs[i][0]]+ABs[i][1])
                
    print((dp_table[N][H]))
    
solve()
# Original solution
H,N = list(map(int,input().split()))
MAXH = H+10000
DP = [float("inf")]*MAXH
DP[0] = 0
a = [0]*N
b = [0]*N
for i in range(N):
  a[i],b[i] = list(map(int,input().split()))
for i in range(MAXH):
  if DP[i] == float("inf"):
    continue    
  for j in range(N):
        DP[min(i+a[j],H)] = min(DP[min(i+a[j],H)],DP[i]+b[j])
print((DP[H]))

# Optimized solution
H,N = list(map(int,input().split()))
MAXH = H+1
DP = [float("inf")]*MAXH
DP[0] = 0
a = [0]*N
b = [0]*N
for i in range(N):
  a[i],b[i] = list(map(int,input().split()))
for i in range(MAXH):
  if DP[i] == float("inf"):
    continue    
  for j in range(N):
        DP[min(i+a[j],H)] = min(DP[min(i+a[j],H)],DP[i]+b[j])
print((DP[H]))
# Original solution
import sys
import math
input=sys.stdin.readline
INF=1000000000
# A Dynamic Programming based Python Program for 0-1 Knapsack problem 
# Returns the maximum value that can be put in a knapsack of capacity W 
def knapSack(W,l, n):
    
    
    
    min_cost = [[0 for i in range(W+1)] for j in range(n+1)] 
    # fill 0th row with infinity 
    for i in range(W+1): 
        min_cost[0][i] = INF 
  
    # fill 0th column with 0 
    for i in range(1, n+1): 
        min_cost[i][0] = 0
    # now check for each weight one by one and fill the 
    # matrix according to the condition 
    for i in range(1, n+1): 
        for j in range(1, W+1): 
            # wt[i-1]>j means capacity of bag is 
            # less than weight of item 
            if (l[i-1][0] > j): 
                min_cost[i][j] = min(min_cost[i-1][j] ,l[i-1][1])
            # here we check we get minimum cost either 
            # by including it or excluding it 
            else: 
                min_cost[i][j] = min(min_cost[i-1][j], 
                    min_cost[i][j-l[i-1][0]] + l[i-1][1]) 
    
  
    # exactly weight W can not be made by given weights 
    if(min_cost[n][W] == INF): 
        return -1
    else: 
        return min_cost[n][W]

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


# Optimized solution

INF=1000000000
# A Dynamic Programming based Python Program for 0-1 Knapsack problem 
# Returns the maximum value that can be put in a knapsack of capacity W 
def knapSack(W,l, n):
    
    
    
    min_cost = [[0 for i in range(W+1)] for j in range(n+1)] 
    # fill 0th row with infinity 
    for i in range(W+1): 
        min_cost[0][i] = INF 
  
    # fill 0th column with 0 
    for i in range(1, n+1): 
        min_cost[i][0] = 0
    # now check for each weight one by one and fill the 
    # matrix according to the condition 
    for i in range(1, n+1): 
        for j in range(1, W+1): 
            # wt[i-1]>j means capacity of bag is 
            # less than weight of item 
            if (l[i-1][0] > j): 
                min_cost[i][j] = min(min_cost[i-1][j] ,l[i-1][1])
            # here we check we get minimum cost either 
            # by including it or excluding it 
            else: 
                min_cost[i][j] = min(min_cost[i-1][j], 
                    min_cost[i][j-l[i-1][0]] + l[i-1][1]) 
    
  
    # exactly weight W can not be made by given weights 
    if(min_cost[n][W] == INF): 
        return -1
    else: 
        return min_cost[n][W]

h,n=list(map(int,input().split()))
l=list()
for i in range(n):
    a,b=list(map(int,input().split()))
    l.append([a,b])
print(( knapSack(h , l , n) ))
# Original solution
# coding: utf-8
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

H, N = lr()
INF = 10 ** 15
limit = H + 100
dp = [INF] * limit
dp[0] = 0
for _ in range(N):
    a, b = lr()
    for i in range(limit):
        index = i+a
        if index > limit - 1:
            index = limit - 1
        dp[index] = min(dp[index], dp[i] + b)

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


# Optimized solution
# coding: utf-8
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

H, N = lr()
INF = 10 ** 15
limit = H + 100
dp = [INF] * limit
dp[0] = 0
for _ in range(N):
    a, b = lr()
    for i in range(H):
        index = i+a
        if index > limit - 1:
            index = limit - 1
        dp[index] = min(dp[index], dp[i] + b)

answer = min(dp[H:])
print(answer)
# Original solution
from math import ceil,floor,comb,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
import string
import sys
sys.setrecursionlimit(10 ** 7)
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())

h, n = MAP()
a = [0]*n
b = [0]*n
dp = [inf]*(h+1)
dp[0] = 0
# dp[j]: ダメージ>=jとするために必要な魔力の最小値

for i in range(n):
    a[i], b[i] = MAP()

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

print((dp[h]))

# Optimized solution
from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
import string
import sys
sys.setrecursionlimit(10 ** 7)
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())

h, n = MAP()
a = [0]*n
b = [0]*n
dp = [inf]*(h+1)
dp[0] = 0
# dp[j]: ダメージ>=jとするために必要な魔力の最小値

for i in range(n):
    a[i], b[i] = MAP()

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

print((dp[h]))