CodeEff/ECCO huggingface dataset:
# Original solution
INF = float("inf")

H, N, *AB = list(map(int, open(0).read().split()))

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

for i in range(1, len(dp)):
    dp[i] = min(dp[i - a] + b for a, b in zip(*[iter(AB)] * 2))

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

# Optimized solution
H, N, *AB = list(map(int, open(0).read().split()))

dp = [0] * (H + max(AB[::2]))

for i in range(1, len(dp)):
    dp[i] = min(dp[i - a] + b for a, b in zip(*[iter(AB)] * 2))

print((min(dp[H:])))
# Original solution
def rec_z():
    for i in range(N):
        for j in range(Hmax+1):
            if j >= a[i]:
                dp[j] = min(dp[j], dp[j-a[i]] + b[i])
    return min(dp[H:Hmax+1])
 
 
H, N = list(map(int,input().split()))
a = []
b = []
for i in range(N):
    aa, bb = list(map(int, input().split()))
    a.append(aa)
    b.append(bb)
Hmax = H + max(a)
INF = 10**9
dp = [INF for _ in range(Hmax+1)] 
dp[0] = 0
print((rec_z()))

# Optimized solution
from sys import stdin


def rec_z():
    for i in range(N):
        for j in range(Hmax+1):
            if j >= a[i]:
                dp[j] = min(dp[j], dp[j-a[i]] + b[i])
    return min(dp[H:Hmax+1])
 
 
readline=stdin.readline
H, N = list(map(int,readline().split()))
a = []
b = []
for i in range(N):
    aa, bb = list(map(int, readline().split()))
    a.append(aa)
    b.append(bb)
Hmax = H + max(a)
INF = 10**9
dp = [INF for _ in range(Hmax+1)] 
dp[0] = 0
print((rec_z()))
# Original solution
H, N = list(map(int,input().split()))
M = [list(map(int,input().split())) for k in range(N)]
dp = [10**10]*(10**5)
dp[0] = 0
for e in M:
    for k in range(e[0],10**5):
        dp[k] = min(dp[k],dp[k-e[0]]+e[1])
print((min(dp[H:])))


# Optimized solution
H, N = list(map(int,input().split()))
M = []
for k in range(N):
    M.append(list(map(int,input().split())))
dp = [10**9]*(10**5)
dp[0] = 0
for A, B in M:
    for k in range(A+1):
        dp[k] = min(dp[k],B)
    for k in range(A+1,H+1):
        dp[k] = min(dp[k],dp[k-A]+B)
print((dp[H]))
# Original solution
# -*- coding: utf-8 -*-
h,n = list(map(int, input().split()))
ab = [list(map(int, input().split())) for _ in range(n)]

inf = 10**9
dp = [[inf]*(h+1) for _ in range(n+1)]
dp[0][0] = 0
for i in range(n):
    for j in range(h+1):
        k = 0
        while ab[i][0]*k<=h:
            d = j+ab[i][0]*k
            dp[i+1][min(h,d)] = min(dp[i+1][min(h,d)], dp[i][j]+ab[i][1]*k)
            k += 1
        d = j+ab[i][0]*k
        dp[i+1][min(h,d)] = min(dp[i+1][min(h,d)], dp[i][j]+ab[i][1]*k)

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

# Optimized solution
# -*- coding: utf-8 -*-
h,n = list(map(int, input().split()))
ab = [list(map(int, input().split())) for _ in range(n)]

inf = 10**9
dp = [inf]*(h+1)
dp[0] = 0
for i in range(n):
    for j in range(h+1):
        d = min(j+ab[i][0], h)
        dp[d] = min(dp[d], dp[j]+ab[i][1])

res = dp[h]
print(res)
# Original solution
import sys
sys.setrecursionlimit(10**9)

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

for k in range(N):
  magic[k] = list(map(int, input().split()))
  magic[k].append(magic[k][0]/magic[k][1])

magic.sort(key = lambda x: x[2], reverse=True)
ans = [0 for _ in range(H+1)]
visited = [0]
anskouho = []

def solve(start, power, point, maryoku):
  if start >= H:
    anskouho.append(point)
    visited.sort(reverse=True)
    return 0
  elif ans[start] != 0:
    visited.sort(reverse=True)
    return 0
  else:
    visited.append(start)
    ans[start] = point
    solve(start+power, power, point+maryoku, maryoku)

for k in range(N):
  for item in visited:
    solve(item+magic[k][0], magic[k][0], ans[item] + magic[k][1], magic[k][1])

print((min(anskouho)))


# Optimized solution
import sys
sys.setrecursionlimit(10**9)

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

for k in range(N):
  magic[k] = list(map(int, input().split()))
  magic[k].append(magic[k][0]/magic[k][1])

magic.sort(key = lambda x: x[2], reverse=True)
ans = [0 for _ in range(H+1)]
visited = [0]
anskouho = [float('inf')]

def solve(start, power, point, maryoku):
  if start == H:
    print((min(point, min(anskouho))))
    exit()
  elif start > H:
    anskouho.append(point)
    visited.sort(reverse=True)
    return 0
  elif ans[start] != 0:
    visited.sort(reverse=True)
    return 0
  else:
    visited.append(start)
    ans[start] = point
    solve(start+power, power, point+maryoku, maryoku)

for k in range(N):
  for item in visited:
    solve(item+magic[k][0], magic[k][0], ans[item] + magic[k][1], magic[k][1])

print((min(anskouho)))
# Original solution
import sys
sys.setrecursionlimit(10**9)

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

for k in range(N):
  magic[k] = list(map(int, input().split()))
  magic[k].append(magic[k][0]/magic[k][1])

magic.sort(key = lambda x: x[2], reverse=True)
ans = [0 for _ in range(H+1)]
visited = [0]
anskouho = [float('inf')]

def solve(start, power, point, maryoku):
  if start == H:
    print((min(point, min(anskouho))))
    exit()
  elif start > H:
    anskouho.append(point)
    visited.sort(reverse=True)
    return 0
  elif ans[start] != 0:
    visited.sort(reverse=True)
    return 0
  else:
    visited.append(start)
    ans[start] = point
    solve(start+power, power, point+maryoku, maryoku)

for k in range(N):
  for item in visited:
    solve(item+magic[k][0], magic[k][0], ans[item] + magic[k][1], magic[k][1])

print((min(anskouho)))

# Optimized solution
import sys
sys.setrecursionlimit(10**9)

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

for k in range(N):
  magic[k] = list(map(int, input().split()))
  magic[k].append(magic[k][0]/magic[k][1])

magic.sort(key = lambda x: x[2], reverse=True)
ans = [0 for _ in range(H+1)]
visited = [0]
anskouho = [float('inf')]

def solve(start, power, point, maryoku):
  if start == H:
    print((min(point, min(anskouho))))
    exit()
  elif start > H:
    anskouho.append(point)
    #visited.sort(reverse=True)
    return 0
  elif ans[start] != 0:
    #visited.sort(reverse=True)
    return 0
  else:
    visited.append(start)
    ans[start] = point
    solve(start+power, power, point+maryoku, maryoku)

for k in range(N):
  for item in visited:
    solve(item+magic[k][0], magic[k][0], ans[item] + magic[k][1], magic[k][1])

print((min(anskouho)))
# Original solution
H,N = list(map(int,input().split()))
spells = sorted([tuple(map(int,input().split())) for _ in range(N)])
max_a = spells[-1][0]

dp = [10000000000 for _ in range(H + max_a + 1)]
dp[0] = 0

for i in range(1, H + max_a + 1):
  for spell in spells:
    if spell[0] > i:
      break
    else:
      dp[i] = min(dp[i], dp[i - spell[0]] + spell[1])

print((min(dp[H:H + max_a + 1])))


# Optimized solution
H,N = list(map(int,input().split()))
spells = [tuple(map(int,input().split())) for _ in range(N)]
max_a = max(spells)[0]

dp = [0]
for i in range(1, H + max_a + 1):
  try:
    dp.append(min([dp[i - a] + b for a,b in spells if a <= i]))
  except ValueError:
    dp.append(10**8)

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

dp = [float('inf')]*(HP+1) #0~HP
dp[0] = 0
for damage, cost in s:
    for hp in range(HP):
        next_idx = min(hp+damage, HP)
        dp[next_idx] = min(dp[next_idx], dp[hp]+cost)
print((dp[-1]))

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

#dp[damage] := モンスターにdamageを与える最小コスト
dp = [float('inf')]*(HP+1) #0~HP
dp[0] = 0
for damage, cost in s:
    for hp in range(HP):
        next_idx = min(hp+damage, HP)
        dp[next_idx] = min(dp[next_idx], dp[hp]+cost)
print((dp[-1]))
# Original solution
H,N = list(map(int,input().split()))
A = [list(map(int,input().split())) for _ in range(N)]
A.insert(0,[0,0])
INFTY = 10**9
dp = [[INFTY for _ in range(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):
        dp[i][j] = dp[i-1][j]
        dp[i][j] = min(dp[i][j],dp[i][max(0,j-A[i][0])]+A[i][1])
print((dp[N][H]))

# Optimized solution
H,N = list(map(int,input().split()))
A = [list(map(int,input().split())) for _ in range(N)]
INFTY = 10**8
dp = [[INFTY for _ in range(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):
        dp[i][j] = dp[i-1][j]
        if j>=A[i-1][0]:
            dp[i][j] = min(dp[i][j],dp[i][j-A[i-1][0]]+A[i-1][1])
        else:
            dp[i][j] = min(dp[i][j],A[i-1][1])
print((dp[N][H]))
# Original solution
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]))

# Optimized solution
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]))
# Original solution
def solve():
    H,N = list(map(int,input().split()))
    attack = []
    mp = []
    for i in range(N):
        a,b = list(map(int,input().split()))
        attack.append(a)
        mp.append(b)
    
    max_attack = max(attack)
    dp = [[float('inf')] * (H+max_attack) for _ in range(N+1)]

    for i in range(N+1):
        dp[i][0] = 0
    
    for i in range(N):
        for j in range(H+max_attack):
            if j - attack[i] >= 0:
                dp[i+1][j] = min(dp[i+1][j], dp[i][j-attack[i]]+mp[i], dp[i+1][j-attack[i]]+mp[i])
            dp[i+1][j] = min(dp[i+1][j], dp[i][j])
    
    ans = float('inf')
    for i in range(N+1):
        for j in range(H,H+max_attack):
            ans = min(ans, dp[i][j])
    
    print(ans)

if __name__ == '__main__':
    solve()

# Optimized solution
def solve():
    H,N = list(map(int,input().split()))
    ap = []
    mp = []

    for _ in range(N):
        a,b = list(map(int,input().split()))
        ap.append(a)
        mp.append(b)
    
    ap_max = max(ap)
    
    dp = [[float('inf')] * (H+ap_max+1) for _ in range(N+1)]
    for i in range(N+1):
        dp[i][0] = 0
    
    for i in range(N):
        for sum_h in range(H+ap_max+1):
            dp[i+1][sum_h] = min(dp[i][sum_h-ap[i]] + mp[i], dp[i][sum_h])
            dp[i+1][sum_h] = min(dp[i+1][sum_h-ap[i]] + mp[i], dp[i][sum_h])
    
    ans = float('inf')
    for sum_h in range(H, H+ap_max+1):
        ans = min(ans,dp[N][sum_h])

    print(ans)

if __name__ == '__main__':
    solve()
# Original solution
import sys
input = sys.stdin.buffer.readline

def main():
    H,N = list(map(int,input().split()))
    x = []
    ma = 0
    for _ in range(N):
        a,b = list(map(int,input().split()))
        ma = max(ma,a)
        x.append((a,b))
    INF = 10**10
    
    dp = [INF for _ in range(H+ma+1)]
    dp[0] = 0
    for a,b in x:
        for i in range(a,H+ma+1):
            if dp[i-a] != INF:
                dp[i] = min(dp[i],dp[i-a]+b)
    
    print((min(dp[H:])))

if __name__ == "__main__":
    main()

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

def main():
    H,N = list(map(int,input().split()))
    x = []
    ma = 0
    for _ in range(N):
        a,b = list(map(int,input().split()))
        ma = max(ma,a)
        x.append((a,b))
    INF = 10**18
    
    dp = [INF for _ in range(H+ma+1)]
    dp[0] = 0
    for i in range(1,H+ma+1):
        dp[i] = min(dp[i-a]+b for a,b in x)
    
    print((min(dp[H:])))

if __name__ == "__main__":
    main()
# Original solution
import math
#import numpy as np
#"""
h,n=list(map(int,input().split()))
#a=list(map(int,input().split()))
ma=[]
for _ in range(n):
    tmp=list(map(int,input().split()))
    ma.append(tmp)


#"""
#h=10**4
#n=10**3
#ma=[[i,i+1] for i in range(n)]

#ma=sorted(ma,key=lambda x:x[1])
#ma.reverse()
dp=[[float("inf") for _ in range(h+1)] for _ in range(n)]
dp[0][0]=0
for i in range(1,h+1):
    dp[0][i]=math.ceil(i/ma[0][0])*ma[0][1]
#print(np.array(ma))
for i in range(1,n):
    #print("number:{},magic:{}".format(i,ma[i]))
    for j in range(h+1):
        if j<ma[i][0]:
            cal=ma[i][1]
        else:
            #print("sansyo before")
            cal=ma[i][1]+dp[i][j-ma[i][0]]
        #print("j:{},cal:{}".format(j,cal))
        dp[i][j]=min(dp[i-1][j],cal)
    #print()


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

# Optimized solution
import math
#import numpy as np
#"""
h,n=list(map(int,input().split()))
#a=list(map(int,input().split()))


#"""
dp=[[float("inf") for _ in range(h+1)] for _ in range(n)]
dp[0][0]=0
ma=list(map(int,input().split()))
for i in range(1,h+1):
    dp[0][i]=math.ceil(i/ma[0])*ma[1]
#print(np.array(ma))
for i in range(1,n):
    ma=list(map(int,input().split()))
    #print("number:{},magic:{}".format(i,ma[i]))
    for j in range(h+1):
        if j<ma[0]:
            cal=ma[1]
        else:
            #print("sansyo before")
            cal=ma[1]+dp[i][j-ma[0]]
        #print("j:{},cal:{}".format(j,cal))
        dp[i][j]=min(dp[i-1][j],cal)
    #print()


print((dp[-1][-1]))
# Original solution
# E - Crested Ibis vs Monster
H, N = list(map(int, input().split()))
AB = []
for i in range(N):
    a, b = list(map(int, input().split()))
    AB.append([a,b])
AB.sort()

DP = [float('inf') for i in range(2* 10**4+1)]
DP[0] = 0
for i in range(10**4):
    for ab in AB:
        DP[i+ab[0]] = min(DP[i+ab[0]], DP[i] + ab[1])

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


# Optimized solution
# E - Crested Ibis vs Monster
H, N = list(map(int, input().split()))
AB = []
for i in range(N):
    a, b = list(map(int, input().split()))
    AB.append([a,b])
AB.sort()

DP = [float('inf') for i in range(2*10**4 + 1)]
DP[0] = 0
for i in range(H):
    for ab in AB:
        DP[i+ab[0]] = min(DP[i+ab[0]], DP[i] + ab[1])

print((min(DP[H:])))
# Original solution
# E - Crested Ibis vs Monster
H, N = list(map(int, input().split()))
AB = []
for i in range(N):
    a, b = list(map(int, input().split()))
    AB.append((a,b))

max_a = max(AB[i][0] for i in range(N))
DP = [float('inf') for i in range(H + max_a + 1)]
DP[0] = 0
for i in range(1, H + max_a):
    DP[i] = min(DP[i - a] + b for a, b in AB)

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


# Optimized solution
# E - Crested Ibis vs Monster
H, N = list(map(int, input().split()))
AB = []
for i in range(N):
    a, b = list(map(int, input().split()))
    AB.append((a,b))

max_a = max(AB[i][0] for i in range(N))
DP = [10**18 for i in range(H + max_a + 1)]
DP[0] = 0
for i in range(1, H + max_a):
    DP[i] = min(DP[i - a] + b for a, b in AB)

print((min(DP[H:])))
# 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()))

#i番目までの魔法を使い, モンスターの体力をj以上減らすのに必要な魔力の最小値(個数制限なしナップザック)
dp = [[float("inf")]*(H+1) for _ in range(N+1)]
dp[0][0] = 0

for i in range(1, N+1):
    for j in range(H+1):
        if j < A[i-1]:
            dp[i][j] = min(dp[i-1][j], B[i-1])
        else:
            dp[i][j] = min(dp[i-1][j], dp[i][j-A[i-1]]+B[i-1])

print((dp[N][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()))
"""
# i番目までの魔法を使い, モンスターの体力をj以上減らすのに必要な魔力の最小値(個数制限なしナップザック)
dp = [[float("inf")]*(H+1) for _ in range(N+1)]
dp[0][0] = 0

for i in range(1, N+1):
    for j in range(H+1):
        if j < A[i-1]:
            dp[i][j] = min(dp[i-1][j], B[i-1])
        else:
            dp[i][j] = min(dp[i-1][j], dp[i][j-A[i-1]]+B[i-1])

print(dp[N][H])
"""
# メモリ削減(ただし, 計算時間は増えてしまう)
# 配るDPで考える
# モンスターの体力をj減らすのに必要な魔力の最小値
dp = [float("inf")]*(H+10**4)
dp[0] = 0
for i in range(N):
    for j in range(H):
        dp[j+A[i]] = min(dp[j+A[i]], dp[j]+B[i])

ans = float("inf")
for j in range(H, H+10**4):
    ans = min(ans, dp[j])

print(ans)
# Original solution
h,n,*L=list(map(int,open(0).read().split()))
dp=[0]+[9e9]*h
ov=9e9
for a,b in zip(*[iter(L)]*2):
	for i in range(h):
		if a+i>h:
			ov=min(min(dp[i:])+b,ov)
			break
		t=dp[i]+b
		if t<dp[i+a]:
			dp[i+a]=t
print((min(ov,dp[h])))

# Optimized solution
h,n,*L=list(map(int,open(0).read().split()))
dp=[0]*(h+10100)
for i in range(1,h+1):dp[i]=min(dp[i-a]+b for a,b in zip(*[iter(L)]*2))
print((dp[h]))
# Original solution
import sys

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

magics = {}
for a, b in AB:
    for i in range(H // a + 2):
        if min(i * a, H) not in magics:
            magics[min(i * a, H)] = i * b
        else:
            magics[min(i * a, H)] = min(magics[min(i * a, H)], i * b)

sorted_keys = sorted(magics.keys())
dp = [float('inf') for _ in range(H+1)]

for key in sorted_keys:
    dp[key] = min(dp[key], magics[key])

for h in range(H):
    for key in sorted_keys:
        dp[min(h + key, H)] = min(dp[min(h + key, H)], dp[h] + magics[key])

print((dp[-1]))


# Optimized solution
import sys

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

dp = [0 for _ in range(H + max(AB, key=lambda x: x[0])[0])]
for h in range(1, len(dp)):
    dp[h] = min(dp[h-a] + b for a, b in AB)

print((dp[H]))
# Original solution
import sys

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

dp = [[float('inf') for _ in range(H + max(AB)[0] + 1)] for _ in range(N + 1)]
dp[0][0] = 0
for n in range(N):
    for h in range(H + max(AB)[0] + 1):
        if h - AB[n][0] >= 0:
            dp[n + 1][h] = min(dp[n + 1][h - AB[n][0]] + AB[n][1], dp[n][h])
        else:
            dp[n + 1][h] = dp[n][h]

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


# Optimized solution
import sys

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

dp = [float('inf') for _ in range(H + max(AB)[0] + 1)]
dp[0] = 0
for h in range(H + max(AB)[0] + 1):
    for n in range(N):
        if h - AB[n][0] >= 0:
            dp[h] = min(dp[h - AB[n][0]] + AB[n][1], dp[h])

print((min(dp[H:])))
# Original solution
H, N = list(map(int, input().split()))
a, b = list(zip(*(list(map(int, input().split())) for _ in range(N))))
maxA = max(a)

inf = float("inf")
dp = [inf for _ in range(H+maxA+1)]
dp[0] = 0

for j in range(N):
    for i in range(a[j], H+maxA+1):
        dp[i] = min(dp[i], dp[i-a[j]]+b[j])

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

# Optimized solution
H, N = list(map(int, input().split()))
a, b = list(zip(*(list(map(int, input().split())) for _ in range(N))))
maxA = max(a)

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

for j in range(N):
    for i in range(a[j], H+maxA+1):
        dp[i] = min(dp[i], dp[i-a[j]]+b[j])

print((min(dp[H:])))
# Original solution
h, n = list(map(int, input().split()))
inf = 10**12
data = []
for i in range(n):
    data.append(list(map(int, input().split())))
dp = [[inf for i in range(h+1 + 10**4)] for j in range(n+1)]
for i in range(n):
    dp[i][0] = 0
for i in range(n):
    a, b = data[i]
    for j in range(h+1+10**4):
        if j - a >= 0:
            dp[i+1][j] = min(dp[i+1][j-a] + b, dp[i][j])
        else:
            dp[i+1][j] = min(b, dp[i][j])
print((dp[-1][h]))

# Optimized solution
h, n = list(map(int, input().split()))
inf = 10**10
dp = [[inf for i in range(h+1)] for j in range(n+1)]
#dp[i][j] := i番目の魔法まで考えたとき、hpをh減らす最小コスト
dp[0][0] = 0
for i in range(1,n+1):
    damage, cost = list(map(int, input().split()))
    for j in range(h+1):
        if j - damage < 0:
            dp[i][j] = min(cost, dp[i][j], dp[i-1][j])
        else:
            dp[i][j] = min(dp[i][j - damage] + cost, dp[i-1][j])
print((dp[-1][h]))
# Original solution
INF = 2**60 # 無限大を表す値
H, N = list(map(int, input().split()))
AB = []
for i in range(N):
    A, B = list(map(int, input().split()))
    AB.append((A, B))
dp = [INF] * (H + 1)
dp[0] = 0
for A, B in AB:
    for j in range(H+1):
        dp[j] = min(dp[j], dp[max(j-A, 0)] + B)
print((dp[H]))

# Optimized solution
INF = 2**60 # 無限大を表す値
H, N = list(map(int, input().split()))
AB = [list(map(int, input().split())) for i in range(N)]
dp = [INF] * (H + 1)
dp[0] = 0
for A, B in AB:
    for j in range(H+1):
        dp[j] = min(dp[j], dp[max(j-A, 0)] + B)
print((dp[H]))
# Original solution
import sys
input=sys.stdin.readline

def dp(i):
  for a,b in AB:
    T=C[i-a if i>a else 0]+b
    C[i]=T if T<C[i] else C[i]

H,N=list(map(int,input().split()))
AB=[list(map(int,input().split())) for _ in range(N)]
C=[0]+[10**8]*H

for i in range(1,H+1):
  dp(i)

print((C[H]))


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

def main():
  def dp(i):
    for a,b in AB:
      T=C[i-a if i>a else 0]+b
      C[i]=T if T<C[i] else C[i]

  H,N=list(map(int,input().split()))
  AB=[list(map(int,input().split())) for _ in range(N)]
  C=[0]+[10**8]*H

  for i in range(1,H+1):
    dp(i)

  print((C[H]))

if __name__=='__main__':
	main()
# Original solution
#import numpy as np

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

a = []
b = []
m = []
for i in range(n):
    at, bt = list(map(int, input().split())) # a_tmp, b_tmp
    a.append(at)
    b.append(bt)

#dp = np.zeros((n+1,h+1))
dp = [[0]*(h+1) for _ in range(n+1)]
for i in range(n):
    for j in range(h):
        # print("Test")
        if j - a[i] < 0:
            o = b[i]
        else:
            o = dp[i+1][j+1-a[i]] + b[i]
        if i != 0:
            dp[i+1][j+1] = min(dp[i][j+1], o)
        else:
            dp[i+1][j+1] = o

print((int(dp[n][h])))


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

a = []
b = []
m = []
for i in range(n):
    at, bt = list(map(int, input().split())) # a_tmp, b_tmp
    a.append(at)
    b.append(bt)

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

print((int(dp[n][h])))
# Original solution
h,n=list(map(int,input().split()))
dp=[10**9]*(h+1)
dp[0]=0
for i in range(n):
    a,b=list(map(int,input().split()))
    for j in range(h):
        k=min(j+a,h)
        dp[k]=min(dp[k],dp[j]+b)
print((dp[h]))
#写経ABC153E

# Optimized solution
h,n=list(map(int,input().split()))
dp=[10**9]*(h+1)
dp[0]=0
for i in range(n):
    a,b=list(map(int,input().split()))
    for j in range(h):
        k=min(j+a,h)
        dp[k]=min(dp[k],dp[j]+b)
print((dp[h]))
# Original solution
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)

dp=[0]
AM=max(A)
BM=max(B)
for i in range(1,H+AM):
    dcand=dp[-1]+BM
    for j in range(N):
        dcand=min(dcand,B[j]+min(dp[i-A[j]:]))
    dp.append(dcand)

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

# Optimized solution
h, n = list(map(int, input().split()))
magics = [list(map(int, input().split())) for _ in range(n)]
max_a = max(a for a, b in magics)
dp = [0] * (h + max_a)
for i in range(1, h + max_a):
    dp[i] = min(dp[i - a] + b for a, b in magics)
print((dp[h]))