CodeEff/ECCO huggingface dataset:
# Original solution
import sys
import functools


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


@functools.lru_cache(maxsize=None)
def solve(h):
    if h <= 0:
        return 0

    ret_val = float("inf")
    for a, b in AB:
        ret_val = min(ret_val, b + solve(h - a))
    return ret_val


sys.setrecursionlimit(100000)

H, N = inpl()
AB = [inpl() for i in range(N)]
AB.sort(key=lambda ab: (ab[0] / ab[1], -ab[0]), reverse=True)
# print(AB)
print((solve(H)))


# Optimized solution
import sys
import functools


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


@functools.lru_cache(maxsize=None)
def solve(h):
    if h <= 0:
        return 0

    ret_val = float("inf")
    for a, b in AB:
        val = b + solve(h - a)
        if val < ret_val:
            ret_val = val
        else:
            break
    return ret_val


sys.setrecursionlimit(100000)

H, N = inpl()
AB = [inpl() for i in range(N)]
AB.sort(key=lambda ab: (ab[0] / ab[1], -ab[0]), reverse=True)
# print(AB)
print((solve(H)))
# Original solution
h, n = list(map(int, input().split()))
a_list = []
b_list = []

for _ in range(n):
    a, b = list(map(int, input().split()))
    a_list.append(a)
    b_list.append(b)

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

dp[0] = 0
cost = float('inf')
for i in range(h):
    for j in range(n):
        dp[i + a_list[j]] = min(dp[i] + b_list[j], dp[i + a_list[j]])
        if i + a_list[j] >= h:
            cost = min(cost, dp[i + a_list[j]])
print(cost)

# Optimized solution
h, n = list(map(int, input().split()))
a_list = []
b_list = []

for _ in range(n):
    a, b = list(map(int, input().split()))
    a_list.append(a)
    b_list.append(b)

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

dp[0] = 0
for i in range(h):
    for j in range(n):
        dp[i + a_list[j]] = min(dp[i] + b_list[j], dp[i + a_list[j]])
print((min(dp[h:])))
# Original solution
H,N=list(map(int,input().split()))
AB=[]
for i in range(N):
    AB.append(list(map(int,input().split())))
maxA=max(AB)[0]
#dp[i] ひとつ前までの呪文で体力iを削るために必要な最小魔法消費量
dp=[float("inf")]*(H+maxA)
ndp=[float("inf")]*(H+maxA)
dp[0]=0
for j in range(N):
    for i in range(H+1):
        ndp[i]=dp[i]
    cost=AB[j][1]
    fire=AB[j][0]
    for i in range(H+1):
        repeat=0
        while i+fire*repeat<H:
            repeat+=1
            ndp[i+fire*repeat]=min(dp[i]+cost*repeat,ndp[i+fire*repeat])
    dp=ndp[:]

ans=float("inf")
for i in range(H,H+maxA):
    ans=min(ans,dp[i])
print(ans)







# Optimized solution
H,N=list(map(int,input().split()))
AB=[]
for i in range(N):
    AB.append(list(map(int,input().split())))
maxA=max(AB)[0]
#dp[i] 敵に合計iダメージを与えるのに必要な最小魔力量
dp=[float("inf")]*(H+maxA)
dp[0]=0
for i in range(H):
    for fire,cost in AB:
        dp[i+fire]=min(dp[i+fire],dp[i]+cost)

ans=min(dp[H:])
print(ans)
# Original solution
(h, n), *m = [[*list(map(int, i.split()))] for i in open(0)]
dp = [0] + [10**9] * h
for i in range(1, h + 1):
    for a, b in m:
        dp[i] = min(dp[i], dp[max(i-a,0)]+b)
print((dp[-1]))


# Optimized solution
(h, n), *m = [[*list(map(int, i.split()))] for i in open(0)]
dp = [0] * 20001
for i in range(1, h + 1):
    dp[i] = min(dp[i-a]+b for a, b in m)
print((dp[h]))
# Original solution
(h, n), *m = [[*list(map(int, i.split()))] for i in open(0)]
dp = [0] * 20001
for i in range(1, h + 1):
    dp[i] = 10**9
    for a, b in m:
        dp[i] = min(dp[i], dp[i-a]+b)
print((dp[h]))


# Optimized solution
(h, n), *m = [[*list(map(int, i.split()))] for i in open(0)]
dp = [0] * 20001
for i in range(1, h + 1):
    dp[i] = min(dp[i-a]+b for a, b in m)
print((dp[h]))
# Original solution
H, N=list(map(int, input().split()))
dp=[0]+[float('inf') for _ in range(2*10**4)]
for _ in range(N):
  a, b=list(map(int, input().split()))
  for i in range(a, H+a):
    dp[i]=min(dp[i-a]+b, dp[i])
    
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]+[float('inf') for _ in range(2*10**4)]
for a, b in AB:
  for i in range(a, H+a):
    dp[i]=min(dp[i-a]+b, dp[i])
    
print((min(dp[H:])))
# Original solution
# coding: utf-8
H,N=list(map(int,input().split()))
AB=[[0,0]]
for i in range(N):
    AB.append(list(map(int,input().split())))

INF=10**9

dp=[[INF for i in range(H+1)] for j 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]=min(dp[i-1][j],dp[i-1][max(j-AB[i][0],0)] + AB[i][1],dp[i][max(j-AB[i][0],0)] + AB[i][1])
        #print(dp[i-1][j],dp[i-1][max(j-AB[i][0],0)] + AB[i][1],dp[i][max(j-AB[i][0],0)] + AB[i][1])
        


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


# Optimized solution
# coding: utf-8
H,N=list(map(int,input().split()))
AB=[[0,0]]
for i in range(N):
    AB.append(list(map(int,input().split())))

INF=10**9

dp=[[INF for i in range(H+1)] for j 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]=min(dp[i-1][j],dp[i][max(j-AB[i][0],0)] + AB[i][1])
        #print(dp[i-1][j],dp[i-1][max(j-AB[i][0],0)] + AB[i][1],dp[i][max(j-AB[i][0],0)] + AB[i][1])
        


print((dp[N][H]))
# Original solution
# coding: utf-8
H,N=list(map(int,input().split()))
AB=[[0,0]]
for i in range(N):
    AB.append(list(map(int,input().split())))

INF=10**9

dp=[[INF for i in range(H+1)] for j 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]=min(dp[i-1][j],dp[i][max(j-AB[i][0],0)] + AB[i][1])
        #print(dp[i-1][j],dp[i-1][max(j-AB[i][0],0)] + AB[i][1],dp[i][max(j-AB[i][0],0)] + AB[i][1])
        


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


# Optimized solution
# coding: utf-8
H,N=list(map(int,input().split()))
AB=[[0,0]]
for i in range(N):
    AB.append(list(map(int,input().split())))
 
INF=10**9

dp=[INF for i in range(H+1)]
dp[0]=0

for i in range(1,N+1):
    for j in range(1,H+1):
        dp[j]=min(dp[j],dp[max(0,j-AB[i][0])] + AB[i][1])

print((dp[H]))
# Original solution
# coding: utf-8
H,N=list(map(int,input().split()))
AB=[[0,0]]
for i in range(N):
    AB.append(list(map(int,input().split())))
 
INF=10**9

dp=[INF for i in range(H+1)]
dp[0]=0

for i in range(1,N+1):
    for j in range(1,H+1):
        dp[j]=min(dp[j],dp[max(0,j-AB[i][0])] + AB[i][1])

print((dp[H]))

# Optimized solution
# coding: utf-8
H,N=list(map(int,input().split()))
AB=[[0,0]]
for i in range(N):
    AB.append(list(map(int,input().split())))
 
INF=10**9

dp=[INF for i in range(H+1)]
dp[0]=0

for i in range(1,N+1):
    damage ,mp = AB[i]
    
    for j in range(1,H+1):
        dp[j]=min(dp[j],dp[max(0 , j - damage)] + mp)

print((dp[H]))
# Original solution
h,n = list(map(int,input().split()))
skills = []
for _ in range(n):
  a,b = list(map(int,input().split()))
  skills.append((a,b))
dp = [float('inf') for _ in range(h+max(skills,key=lambda x:x[1])[1] + 1)]
dp[0] = 0
  
for i in range(len(dp)):
  if dp[i] ==float('inf'):
    continue
  for damage,mp in skills:
    if i+damage >= len(dp):
      continue
    if dp[i+damage] > dp[i] + mp:
      dp[i+damage] = dp[i]+mp
ans = min([x for x in dp[h:] if x>0])
print(ans)
#print(dp)



# Optimized solution
h,n = list(map(int,input().split()))
magic = []
maxa = 0
for _ in range(n):
  a,b = list(map(int,input().split()))
  maxa = max(maxa,a)
  magic.append((a,b))
#magic.sort()

dp = [float('inf') for _ in range(h + maxa)]
dp[0] = 0

for i in range(h):
  for a,b in magic:
    if i+a > h+maxa:
      continue
    dp[i+a] = min(dp[i] + b,dp[i+a])
print((min(dp[h:])))
# Original solution
h,n = list(map(int,input().split()))
now = [10**10 for _ in range(h+1)]
now[0] = 0
for _ in range(n):
  a,b = list(map(int,input().split()))
  for i in range(1,h+1):
    if i - a < 0:
      now[i] = min(now[i],b)
    else:
      now[i] = min(now[i],now[i-a]+b)
print((now[-1]))

# Optimized solution
h,n = list(map(int,input().split()))
now = [10**10 for _ in range(h+1)]
now[0] = 0
for _ in range(n):
  a,b = list(map(int,input().split()))
  for i in range(1,h+1):
    if i - a >= 0:
      now[i] = min(now[i],now[i-a]+b)
    else:
      now[i] = min(now[i],b)
print((now[-1]))
# Original solution
#!/usr/bin python3
# -*- coding: utf-8 -*-

h, n = list(map(int, input().split()))
ab = set([])
for _ in range(n):
    ab.add(tuple(map(int,input().split())))
l = h + max(a for a, _ in ab)

#DP[i] = i までの魔法でモンスターの体力を減らすため消耗する魔力の最小値
dp = [10**8+1] * l
dp[0] = 0

for i in range(l):  #最大L回繰り返せばよい
    for a, b in ab:
        dp[i] = min(dp[i-a] + b, dp[i])
print((min(dp[h:])))


# Optimized solution
#!/usr/bin python3
# -*- coding: utf-8 -*-

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

#DP[i] = i までの魔法でモンスターの体力を減らすため消耗する魔力の最小値
dp = [0] * 20001

for i in range(h):
    dp[i] = min(dp[i-a] + b for a, b in ab)
print((dp[h-1]))
# Original solution
H, N = list(map(int, input().split()))
hpdown = list()
mpdown = list()
for i in range(N):
  a, b = list(map(int, input().split()))
  hpdown.append(a)
  mpdown.append(b)
  
hmax = max(max(mpdown)*2+1, H+max(mpdown)+1)
dp = [10 ** 9] * (hmax)
dp[0] = 0
for h in range(1, hmax):
  for n in range(N):
    if(h-hpdown[n]>=0):
      dp[h] = min(dp[h], dp[h-hpdown[n]] + mpdown[n])
      
ans = 10 ** 9
for i in range(H, hmax):
  if(dp[i] < ans):
    ans = dp[i]
print(ans)

# Optimized solution
H, N = list(map(int, input().split()))
hpdown = list()
mpdown = list()
for i in range(N):
  a, b = list(map(int, input().split()))
  hpdown.append(a)
  mpdown.append(b)
  
hmax = H+(max(hpdown)+1)
dp = [10 ** 9] * (hmax)
dp[0] = 0
for h in range(1, hmax):
  for n in range(N):
    if(h-hpdown[n]>=0):
      dp[h] = min(dp[h], dp[h-hpdown[n]] + mpdown[n])
      
ans = 10 ** 9
for i in range(H, hmax):
  if(dp[i] < ans):
    ans = dp[i]
print(ans)
# Original solution
h,n = list(map(int,input().split()))

ls = [list(map(int,input().split())) for _ in range(n)]

amax = max(a for a,b in ls)

dp = [0]*(h+amax)

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

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



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

ls = [list(map(int,input().split())) for _ in range(n)]

amax = max(a for a,b in ls)

dp = [0]*(h+amax)

for i in range(1,h+amax):
  dp[i] = min(dp[i-a]+b for a,b in ls)

print((min(dp[h:])))
# Original solution
import sys
import heapq
def I(): return int(sys.stdin.readline())
def LI(): return [int(x) for x in sys.stdin.readline().split()]

def main():
    H,N = LI()
    M = []
    for i in range(N):
        M.append(LI())

    dp = {0:H}
    h = []
    heapq.heappush(h,0)
    nxt = -1

    for i in range(10**9):
        if dp.get(i,-1) == -1:
            continue
        if dp[i] == 0:
            print(i)
            return
        for j in range(N):
            dp[i+M[j][1]] = min(dp.get(i+M[j][1],H),max(0,dp[i]-M[j][0]))

if __name__ == "__main__":
    main()


# Optimized solution
import sys
import heapq
def I(): return int(sys.stdin.readline())
def LI(): return [int(x) for x in sys.stdin.readline().split()]

def main():
    H,N = LI()
    M = []
    for i in range(N):
        M.append(LI())

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

    for i in range(H):
        for j in range(N):
            HP = min(H,i+M[j][0])
            dp[HP] = min(dp[HP],dp[i]+M[j][1])
    print((dp[H]))

if __name__ == "__main__":
    main()
# Original solution

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

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


dp[0][0]=0

for i in range(n):
    # print(dp)
    for j in range(h+1):
        # print("i+1=",i+1,"j=",j)
        dp[i+1][j]=min(dp[i+1][j],dp[i][j])
        dp[i+1][min(h,j+a[i])]=min(dp[i+1][min(h,j+a[i])],dp[i+1][j]+b[i])
        # print(i+1,j,min(h,j+a[i]),"\n",dp)
    # print("==================")

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


# Optimized solution
def LI():
  return list(map(int,input().split()))
h,n=LI()

a=[]
b=[]
for _ in range(n):
  x,y=LI()
  a.append(x)
  b.append(y)
  
INF=10**15
dp=[INF]*(h+max(a)+10)
dp[0]=0
for i in range(0,h+1):
  for j,k in zip(a,b):
    dp[i+j]=min(dp[i+j],dp[i]+k)

ans=INF
for i in dp[h:]:
  ans=min(ans,i)
print(ans)
# Original solution
import sys
f=lambda:list(map(int,sys.stdin.readline().split()))
h,n=f()
INF=10**9
dp=[[INF]*(h+1) for _ in range(n+1)]
dp[0][0]=0
for i in range(n):
  a,b=f()
  for j in range(h+1):
    dp[i+1][j]=min(dp[i][j],dp[i+1][max(j-a,0)]+b)
print((dp[n][h]))

# Optimized solution
import sys
f=lambda:list(map(int,sys.stdin.readline().split()))
h,n=f()
dp=[10**9]*(h+1)
dp[0]=0
for i in range(n):
  a,b=f()
  for j in range(h+1):
    dp[j]=min(dp[j],dp[max(j-a,0)]+b)
print((dp[h]))
# Original solution
import sys
f=lambda:list(map(int,sys.stdin.readline().split()))
h,n=f()
dp=[10**9]*(h+1)
dp[0]=0
for i in range(n):
  a,b=f()
  for j in range(h+1):
    dp[j]=min(dp[j],dp[max(j-a,0)]+b)
print((dp[h]))

# Optimized solution
f=lambda:list(map(int,input().split()))
h,n=f()
dp=[0]+[10**9]*h
for i in range(n):
  a,b=f()
  for j in range(h+1): dp[j]=min(dp[j],dp[max(j-a,0)]+b)
print((dp[h]))
# Original solution
H, N = list(map(int, input().split()))
magic = [list(map(int, input().split())) for _ in range(N)]


max_magic = 0
for a, _ in magic:
    max_magic = max(max_magic, a)

amount = H + 1
dp = [float('inf')] * (amount + max_magic)
dp[0] = 0

ret = float('inf')

for amt in range(1, amount + max_magic):
    t = [dp[amt - a] + b if amt - a >= 0 else float('inf') for a, b in magic]
    dp[amt] = min(t)

    if amt >= H:
        ret = min(dp[amt], ret)

print(ret)


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


max_magic = 0
for a, _ in magic:
    max_magic = max(max_magic, a)

amount = H + 1
dp = [0] * (amount + max_magic)
dp[0] = 0

ret = float('inf')

for amt in range(1, amount + max_magic):
    t = [dp[amt - a] + b for a, b in magic]
    dp[amt] = min(t)

    if amt >= H:
        ret = min(dp[amt], ret)

print(ret)
# Original solution
import sys
input = sys.stdin.readline
H, N = list(map(int, input().split()))
a = []
for _ in range(N):
  u, v = list(map(int, input().split()))
  a.append((u, v))
dp = [float("inf")] * (H + 1)
dp[H] = 0
for i in range(N):
  for j in range(H, -1, -1):
    dp[max(j - a[i][0], 0)] = min(dp[max(j - a[i][0], 0)], dp[j] + a[i][1])
print((dp[0]))

# Optimized solution
import sys
input = sys.stdin.readline
H, N = list(map(int, input().split()))
dp = [float("inf")] * (H + 1)
dp[H] = 0
for _ in range(N):
  a, b = list(map(int, input().split()))
  for x in range(H, -1, -1):
    dp[max(0, x - a)] = min(dp[max(0, x - a)], dp[x] + b)
print((dp[0]))
# 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()))
dp = [float('inf')]*(h+1)
dp[0] = 0

for i in range(n):
    for j in range(h+1):
        if dp[j] != float('inf'):
            nj = j + a[i]
            if nj >= h:
                nj = h
            dp[nj] = min(dp[nj],dp[j] + b[i])
print((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 = [1e100]*(h+1)
dp[0] = 0

for i in range(n):
    for j in range(h+1):
        if dp[j] != 1e100:
            nj = j + a[i]
            if nj >= h:
                nj = h
            dp[nj] = min(dp[nj],dp[j] + b[i])
print((dp[h]))
# Original solution
h,n = list(map(int,input().split()))

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

dp = [10**10]*(h+ma+1)
dp[0] = 0

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

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

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

ab = [list(map(int,input().split())) for i in range(n)]
ma = max(a for a,b in ab)


dp = [10**10]*(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 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()))
ma = max(A)
dp = [float("inf")] * (H + ma)
dp[0] = 0
for i in range(N):
    a = A[i]
    b = B[i]
    for j in range(1, H + ma):
        dp[j] = min(dp[j - a] + b, dp[j])
print((min(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()))
ma = max(A)
dp = [0] * (H + ma)
dp[0] = 0
for i in range(N):
    a = A[i]
    b = B[i]
    for j in range(1, H + ma):
        if dp[j] == 0:
            dp[j] = dp[j - a] + b
        else:
            dp[j] = min(dp[j - a] + b, dp[j])
print((min(dp[H:])))
# Original solution
import math
import sys
input = sys.stdin.readline
def main():
	H,N = list(map(int,input().split()))
	A,B = [],[]
	ap = A.append
	bp = B.append
	for _ in range(N):
		a,b = list(map(int,input().split()))
		ap(a)
		bp(b)
	
	dp = [[0 for _ in range(H+1)] for _ in range(N)]
	
	for i in range(1,H+1):
		dp[0][i] = math.ceil(i/A[0])*B[0]

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

	print((dp[N-1][H]))
if __name__ == '__main__':
	main()

# Optimized solution
import math
import sys
input = sys.stdin.readline
def main():
	H,N = list(map(int,input().split()))
	A,B = [],[]
	ap = A.append
	bp = B.append
	for _ in range(N):
		a,b = list(map(int,input().split()))
		ap(a)
		bp(b)
	
	dp = [[0 for _ in range(H+1)] for _ in range(N)]
	
	for i in range(1,H+1):
		dp[0][i] = math.ceil(i/A[0])*B[0]

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

	print((dp[N-1][H]))
if __name__ == '__main__':
	main()
# Original solution
from collections import defaultdict
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 = defaultdict(lambda : 10**10)
dp[0] = 0

for i in range(0,N):
    ndp = dp.copy()
    a = A[i]
    b = B[i]
    for h,m in list(dp.items()):
        cnt = 0
        while True:
            damage = h+a*cnt
            if damage >= H:
                ndp[H] = min(ndp[H], ndp[h] + b*cnt)
                break
            ndp[damage] = min(ndp[damage], ndp[h] + b*cnt)
            cnt += 1
    dp = ndp

print((dp[H]))




# Optimized solution
from collections import defaultdict
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 = [10**10]*(H+1)
dp[0] = 0

for i in range(0,N):
    a = A[i]
    b = B[i]
    for h in range(H+1-a):
        dp[h+a] = min(dp[h+a], dp[h] + b)
    dp[H] = min(dp[H], min(dp[H-a:H])+b)

print((dp[H]))
# Original solution
h,n=list(map(int,input().split()))
a=[]
ab=[]

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

loop=h+max(a)
cost=[-1 for i in range(loop)]
cost[0]=0
i=0
costlist=[]
while i<loop:
    costlist.clear()
    for j in range(n):
        ii=i-ab[j][0]
        if (0<=ii<h)&(cost[ii]>=0):
            costlist.append(cost[ii]+ab[j][1])
    if len(costlist)!=0:
        cost[i]=min(costlist)
    i+=1
acost=[i for i in cost[h:] if i!=-1]
ans=min(acost)
print(ans)

# Optimized solution
h,n=list(map(int,input().split()))
a=[]
ab=[]

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

loop=h+max(a)
cost=[-1 for i in range(loop)]
cost[0]=0
i=0
costlist=[]
while i<loop:
    costlist=[]
    for j in range(n):
        ii=i-ab[j][0]
        if (0<=ii<h)&(cost[ii]>=0):
            costlist.append(cost[ii]+ab[j][1])
    if len(costlist)!=0:
        cost[i]=min(costlist)
    i+=1
acost=[i for i in cost[h:] if i!=-1]
ans=min(acost)
print(ans)
# Original solution
h,n = [int(i) for i in input().split()]
l = [[int(i) for i in input().split()] for _ in range(n)]

inf = float('inf')
memo = [inf for _ in range(h+1)]
memo[0] = 0
for i in range(h+1):
    for x,y in l:
        # これめっちゃ大事やん
        j = min(i+x, h)
        memo[j] = min(memo[j],memo[i] + y)
print((memo[-1]))




# Optimized solution
h,n = [int(i) for i in input().split()]
l = [[int(i) for i in input().split()] for _ in range(n)]
 
inf = float('inf')
memo = [inf for _ in range(h+1)]
memo[0] = 0
for i in range(h+1):
    for x,y in l:
        j = min(i+x, h)
        memo[j] = min(memo[j],memo[i] + y)
print((memo[-1]))
# Original solution

def main():
    H, N = [int(x) for x in input().split()]
    magic = [list(map(int, input().split())) for _ in range(N)]
    # print(magic)
    max_a = max(a for a, _ in magic)
    dp = [float("inf") for _ in range(H + max_a)]
    dp[0] = 0

    for i in range(1, H+max_a):
        dp[i] = min(dp[i-a] + b for a, b in magic)

    ans = min(dp[H:H+max_a])
    print(ans)


if __name__ == '__main__':
    main()

# Optimized solution
def main():
    H, N = [int(x) for x in input().split()]
    magic = [list(map(int, input().split())) for _ in range(N)]
    # print(magic)
    max_a = max(a for a, _ in magic)
    dp = [10**18 for _ in range(H + max_a)]
    dp[0] = 0

    for i in range(1, H+max_a):
        dp[i] = min(dp[i-a] + b for a, b in magic)

    ans = min(dp[H:H+max_a])
    print(ans)


if __name__ == '__main__':
    main()
# Original solution
H, N = list(map(int, input().split()))
AB = [list(map(int, input().split())) for _ in range(N)]

max_ab = max(AB)
dp = [-1]*(H+max_ab[0]+1)
dp[0] = 0

for i in range(1, H + max_ab[0]):
    lst = [dp[i-AB[j][0]] + AB[j][1] for j in range(N) if (i >= AB[j][0] and dp[i-AB[j][0]]!=-1)]
    if lst!=[]:dp[i] = min(lst)

print((min([i for i in dp[H:-1] if i!=-1])))
               

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

max_ab = max(AB)
dp = [10**10]*(H+max_ab[0])
dp[0] = 0

for i in range(1, H + max_ab[0]):
    dp[i] = min(dp[i - a] + b for a, b in AB)

print((min(dp[H:])))
# Original solution
import sys
input = sys.stdin.readline

H, N = list(map(int, input().split(" ")))
dp = [[float('inf') for i in range(H + 1)] for j in range(N + 1)]
for i in range(N + 1):
    dp[i][0] = 0

for i in range(N):
    A, B = list(map(int, input().split(" ")))
    for j in range(H + 1):
        dp[i + 1][j] = min(dp[i + 1][j], dp[i][j])
        dp[i][min(j + A, H)] = min(dp[i][min(j + A, H)], dp[i][j] + B)
print((dp[N][H]))

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

H, N = list(map(int, input().split(" ")))
dp = [float('inf') for i in range(H + 1)]
dp[0] = 0

for i in range(N):
    A, B = list(map(int, input().split(" ")))
    for j in range(H + 1):
        if dp[j] != float('inf'):
            dp[min(j + A, H)] = min(dp[min(j + A, H)], dp[j] + B)
print((dp[H]))
# Original solution
import math
import sys

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


cost = [100000000 for _ in range(H)]
min_cost = 100000000

cost[0] = 0

attack_num = 0
for k in range(H):
    for j in range(N):
        if k + AB[j][0] >= H:
            if min_cost > cost[k] + AB[j][1] :
                min_cost = cost[k] + AB[j][1]
        else:
            if cost[k+AB[j][0]] > cost[k] + AB[j][1]:
                cost[k+AB[j][0]] = cost[k] + AB[j][1]
print(min_cost)                


# Optimized solution

def main():
    H, N = list(map(int,input().split()))
    AB = [list(map(int,input().split())) for i in range(N)]
    
    cost = [100000000 for _ in range(H)]
    min_cost = 100000000
    
    cost[0] = 0
    
    for k in range(H):
        for j in range(N):
            if k + AB[j][0] >= H:
                kari1 = cost[k] + AB[j][1]
                if min_cost > kari1:
                    min_cost = kari1
            else:
                kari2 = cost[k] + AB[j][1]
                if cost[k+AB[j][0]] > kari2:
                    cost[k+AB[j][0]] = kari2
    print(min_cost)

if __name__=='__main__':
    main()