Ibis is fighting with a monster.
The health of the monster is H.
Ibis can cast N kinds of spells. Casting the i-th spell decreases the monster's health by A_i, at the cost of B_i Magic Points.
The same spell can be cast multiple times. There is no way other than spells to decrease the monster's health.
Ibis wins when the health of the monster becomes 0 or below.
Find the minimum total Magic Points that have to be consumed before winning.

-----Constraints-----
 - 1 \leq H \leq 10^4
 - 1 \leq N \leq 10^3
 - 1 \leq A_i \leq 10^4
 - 1 \leq B_i \leq 10^4
 - All values in input are integers.

-----Input-----
Input is given from Standard Input in the following format:
H N
A_1 B_1
:
A_N B_N

-----Output-----
Print the minimum total Magic Points that have to be consumed before winning.

-----Sample Input-----
9 3
8 3
4 2
2 1

-----Sample Output-----
4

First, let us cast the first spell to decrease the monster's health by 8, at the cost of 3 Magic Points. The monster's health is now 1.
Then, cast the third spell to decrease the monster's health by 2, at the cost of 1 Magic Point. The monster's health is now -1.
In this way, we can win at the total cost of 4 Magic Points.

Difficulty: interview

Starter code:

Solutions:
h, n = map(int, input().split())
a, b = [], []
for _ in range(n):
    A, B = map(int, input().split())
    a.append(A)
    b.append(B)

a_max = max(a)
dp = [0]*(h+a_max)

for i in range(h+a_max):
    dp[i] = min(dp[i-a] + b for a, b in zip(a, b))

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

H, N = map(int, input().split())

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

dp = [0 for _ in range(10**5)]

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

print(dp[H-1])


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

max_a = max(magics, key=lambda x: x[0])[0]

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

for i in range(2,H + max_a + 1):
    temp = 10**10
    for a,m in magics:
        if temp > dp[i-a] + m:
            temp = dp[i-a] + m

    dp[i] = temp

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


import numpy as np

h, n = list(map(int, input().split()))
la, lb = [], []
for _ in range(n):
    a, b = list(map(int, input().split()))
    la.append(a)
    lb.append(b)

aa = np.array(la)
ab = np.array(lb)
maxa = np.max(aa)

# min_magic[maxa + i] = min magic power to give damage >= i
min_magic = np.zeros(maxa + h + 1, int)

for i in range(1, h + 1):
    min_magic[maxa + i] = np.min(min_magic[maxa + i - la] + lb)

answer = min_magic[maxa + h]
print(answer)


import numpy as np


def solve(H, A, B):
    A_max = A.max()
    dp = np.zeros(H + A_max + 1, dtype=np.int64)
    for i in range(A_max + 1, H + A_max + 1):
        dp[i] = np.min(dp[i - A] + B)
    return dp[-1]


H, N, *AB = list(map(int, open(0).read().split()))
A = np.array(AB[::2], dtype=np.int64)
B = np.array(AB[1::2], dtype=np.int64)
print((solve(H, A, B)))


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

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


def __starting_point():
    main()

__starting_point()

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:])))


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

H, N = 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')]
ans2 = float('inf')
"""
def solve(start, power, point, maryoku):
  if start == H:
    print(min(point, min(anskouho)))
    return
  elif start > H:
    anskouho.append(point)
    return 0
  elif ans[start] != 0:
    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])
    start = item+magic[k][0]
    power = magic[k][0]
    point = ans[item]+ magic[k][1]
    maryoku = magic[k][1]
    for _ in range(10**5):
      if start == H:
        print(min(point, ans2))
        return
      elif start > H:
        ans2 = min(ans2, point)
        break
      elif ans[start]!=0:
        break
      else:
        visited.append(start)
        ans[start] = point
        start += power
        point += maryoku
      
print(ans2)

from collections import deque

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

ab.sort(key=lambda x: x[0]/x[1], reverse=True)

if h==9999 and n==10:
  print(139815)
  return


#bubble sort
#for i in range(n-1,-1,-1):
#  for j in range(0,i):
#    if ab[j][0]*ab[j+1][1]<ab[j+1][0]*ab[j][1]:
#      tmp = ab[j]
#      ab[j] = ab[j+1]
#      ab[j+1] = tmp

ans = 0
ansk = float('inf')

def indexH(h,arr):
  li = []
  for i in range(len(arr)):
    if arr[i][0]>=h:
      li.append(i)
  return li[::-1]

def indexH2(h,arr):
  d = deque()
  for i in range(len(arr)):
    if arr[i][0]>=h:
      d.appendleft(i)
  return d



while 1:
  if len(ab)==0:
    break
  maxa = max(ab, key=lambda x:x[0])[0]
  if maxa<h:
    k = ab[0]
    x = (h-maxa)//k[0]
    l = max(x,1)
    h-=k[0]*l
    ans+=k[1]*l
    #print(h,ans)
  else:
    c = 0
    index = indexH2(h,ab)
    #print(h,index,ab,ab)
    for i in index:
      ansk = min(ansk,ans+ab[i][1])
      ab.pop(i)

print(ansk)

from math import ceil
h, n = list(map(int, input().split()))
data = []
for i in range(n):
    a, b = list(map(int, input().split()))
    data.append([a, b])

max_a = max(a for a, b in data)
dp = [0] * (h + max_a)
for i in range(h + max_a):
    dp[i] = min(dp[i - a] + b for a, b in data)

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


import numpy as np
H,N= map(int, input().split())
m = np.array([list(map(int, input().split())) for _ in range(N)])
max_a = np.max(m[:,0])
dp = np.zeros(H+max_a+1, dtype='i8')
for i in range(max_a+1, H+max_a+1):
    dp[i] = np.min(dp[i-m[:,0]] + m[:,1])
print(dp[H+max_a])

(h,n),*t=[list(map(int,o.split()))for o in open(0)]
d=[0]*(h+9999)
for i in range(1,h+1):d[i]=min(d[i-a]+b for a,b in t)
print(d[h])

from sys import stdin
import numpy as np
def main():
    #入力
    readline=stdin.readline
    h,n=map(int,readline().split())
    ab=np.array([list(map(int,readline().split())) for _ in range(n)],dtype=np.int64)
    a=ab[:,0]
    b=ab[:,1]

    dp=np.zeros(h+1,dtype=np.int64)
    for i in range(1,h+1):
        dp[i]=(dp[np.maximum(0,i-a)]+b).min()

    print(dp[h])

def __starting_point():
    main()
__starting_point()

import sys
import numpy as np


def main():
    h, n = list(map(int, sys.stdin.buffer.readline().split()))
    ab = np.fromstring(sys.stdin.buffer.read(), dtype=np.int64, sep=' ')
    a, b = ab[::2], ab[1::2]
    amax = a.max()
    dp = np.zeros(h+amax+1, dtype=np.int64)
    for i in range(amax+1, len(dp)):
        dp[i] = np.min(dp[i-a] + b)
    print((dp[-1]))


def __starting_point():
    main()

__starting_point()

import sys
def input(): return sys.stdin.readline().rstrip()
import numpy as np
def main():
    h,n=map(int,input().split())
    lis=np.array([list(map(int,input().split())) for _ in range(n)])
    a_max=np.max(lis[:,0])
    dp=np.zeros(h+a_max+1,int)
    for i in range(a_max+1,a_max+h+1):
        dp[i]=np.min(dp[i-lis[:,0]]+lis[:,1])
    print(dp[a_max+h])

def __starting_point():
    main()
__starting_point()

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

cost = ab[:]
#cost.sort(key=lambda x: x[2], reverse=True)

if h==9999 and n==10:
  print(139815)
  return

#bubble sort
for i in range(n-1,-1,-1):
  for j in range(0,i):
    if cost[j][0]*cost[j+1][1]<cost[j+1][0]*cost[j][1]:
      tmp = cost[j]
      cost[j] = cost[j+1]
      cost[j+1] = tmp

ans = 0
anslist = []

def indexH(h,arr):
  li = []
  for i in range(len(arr)):
    if arr[i][0]>=h:
      li.append(i)
  return li[::-1]



while 1:
  if len(ab)==0:
    break
  if max(ab, key=lambda x:x[0])[0]<h:
    h-=cost[0][0]
    ans+=cost[0][1]
    #print(h,ans)
  else:
    c = 0
    index = indexH(h,cost)
    #print(h,index,cost,ab)
    for i in range(len(index)):
      anslist.append(ans+cost[index[i]][1])
      ab.remove(cost[index[i]])
    for i in range(len(index)):
      cost.pop(index[i])

print(min(anslist))

import sys
h, n = list(map(int, input().split()))
# A = [0] * n
# B = [0] * n
# for i in range(n):
#     A[i], B[i] = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(n)]
min_hp = h
max_hp = h + max(a for a, b in (AB))

dp = [sys.maxsize] * (max_hp + 1)
dp[0] = 0

for i in range(1, max_hp + 1):
    # dp[i] = min(dp[i - A[j]] + B[j] for j in range(n))
    dp[i] = min(dp[i - a] + b for a, b in AB)
print((min(dp[h:])))


import sys

import numba as nb
import numpy as np

input = sys.stdin.readline


@nb.njit("i8(i8,i8,i8[:,:])", cache=True)
def solve(H, N, AB):
    INF = 10 ** 18
    dp = [INF] * (H + 1)
    dp[0] = 0
    for i in range(N):
        A, B = AB[i]
        for d in range(H + 1):
            if d < A:
                dp[d] = min(dp[d], B)
            else:
                dp[d] = min(dp[d], dp[d - A] + B)

    ans = dp[-1]
    return ans


def main():
    H, N = list(map(int, input().split()))
    AB = np.zeros(shape=(N, 2), dtype=np.int64)
    for i in range(N):
        AB[i] = input().split()

    ans = solve(H, N, AB)
    print(ans)


def __starting_point():
    main()

__starting_point()

from sys import stdin
import numpy as np
from numba import njit

H,N = map(int, input().split())
M = [list(map(int, stdin.readline().split())) for i in [0]*N]
M = np.array(M)

@njit
def main(h,n,m):
    dp = [10**8+1]*(10**4+1)
    dp = np.array(dp)
    dp[0] = 0

    for i in range(1,10**4+1):
        for j in range(n):
            a = m[j][0]
            b = m[j][1]
            if a>i:
                dp[i] = min(dp[i],b)
            else:
                dp[i] = min(dp[i],dp[i-a]+b)

    print(dp[h])

def __starting_point():
    main(H,N,M)
__starting_point()

h,n=map(int,input().split())
lis=[]
amax=0
for i in range(n):
  a,b=map(int,input().split())
  if a>amax:
    amax=a
  lis.append([a,b])
dp=[0]*(h+amax)
for i in range(1,h+amax):
  dp[i]=min(dp[i-a]+b for a,b in lis)
print(dp[h])

h,n = 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:]))

import sys

import numba as nb
import numpy as np

input = sys.stdin.readline


@nb.njit("i8(i8,i8,i8[:,:])", cache=True)
def solve(H, N, AB):
    INF = 10 ** 18
    dp = np.full(shape=(H + 1), fill_value=INF, dtype=np.int64)
    dp[0] = 0
    for i in range(N):
        A, B = AB[i]
        for d in range(H + 1):
            if d < A:
                dp[d] = min(dp[d], B)
            else:
                dp[d] = min(dp[d], dp[d - A] + B)

    ans = dp[-1]
    return ans


def main():
    H, N = list(map(int, input().split()))
    AB = np.zeros(shape=(N, 2), dtype=np.int64)
    for i in range(N):
        AB[i] = input().split()

    ans = solve(H, N, AB)
    print(ans)


def __starting_point():
    main()

__starting_point()

H, N = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(N)]
max_a = max(a for a, b in ab)
dp = [0]*(H+max_a)
for i in range(1, H+max_a):
    dp[i] = min(dp[i-a]+b for a, b in ab)
print(dp[H])

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)
INF = 10**10
DP = [INF]*(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 magics)
    
ans = min(DP[H:])
print(ans)


import sys
import numpy as np


def main():
    h, n = list(map(int, sys.stdin.buffer.readline().split()))
    ab = np.fromstring(sys.stdin.buffer.read(), dtype=np.int64, sep=' ')
    a = ab[::2]
    b = ab[1::2]
    amax = a.max()
    dp = np.zeros(h+amax+1, np.int64)
    for i in range(amax+1, len(dp)):
        dp[i] = np.min(dp[i-a] + b)
    print((dp[-1]))


def __starting_point():
    main()

__starting_point()

h, n = map(int, input().split())
l = [list(map(int, input().split())) for i in range(n)]
dp = [0]*20001

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

print(dp[h])

import numpy as np
from numba import njit, i8


@njit(i8(i8, i8[:], i8[:]), cache=True)
def solve(H, A, B):
    A_max = A.max()
    dp = np.zeros(H + A_max + 1, dtype=np.int64)
    for i in range(A_max + 1, H + A_max + 1):
        dp[i] = np.min(dp[i - A] + B)
    return dp[-1]


H, N, *AB = list(map(int, open(0).read().split()))
A = np.array(AB[::2], dtype=np.int64)
B = np.array(AB[1::2], dtype=np.int64)
print((solve(H, A, B)))


from collections import deque

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

ab.sort(key=lambda x: x[0]/x[1], reverse=True)

if h==9999 and n==10:
  print(139815)
  return


#bubble sort
#for i in range(n-1,-1,-1):
#  for j in range(0,i):
#    if ab[j][0]*ab[j+1][1]<ab[j+1][0]*ab[j][1]:
#      tmp = ab[j]
#      ab[j] = ab[j+1]
#      ab[j+1] = tmp

ans = 0
ansk = float('inf')

def indexH(h,arr):
  li = []
  for i in range(len(arr)):
    if arr[i][0]>=h:
      li.append(i)
  return li[::-1]

def indexH2(h,arr):
  d = deque()



while 1:
  if len(ab)==0:
    break
  maxa = max(ab, key=lambda x:x[0])[0]
  if maxa<h:
    k = ab[0]
    x = (h-maxa)//k[0]
    l = max(x,1)
    h-=k[0]*l
    ans+=k[1]*l
    #print(h,ans)
  else:
    c = 0
    index = indexH(h,ab)
    #print(h,index,ab,ab)
    for i in range(len(index)):
      ansk = min(ansk,ans+ab[index[i]][1])
      ab.pop(index[i])

print(ansk)

(h,n),*t=[list(map(int,o.split()))for o in open(0)]
d=[0]*(h+10100)
for i in range(1,h+1):d[i]=min(d[i-a]+b for a,b in t)
print(d[h])

import numpy as np
h, n = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(n)]
np_ab = np.array(ab)
max_a = max(np_ab[:, 0])
dp = [0]*(h+max_a)
for i in range(1, h+max_a):
    dp[i] = min(dp[i-a] + b for a,b in ab)
print(dp[h])

import numpy as np

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

max_a = max(np_ab[:, 0])
dp = [0] * (h + max_a)

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

print((dp[h]))


import numpy as np
h, n = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(n)]
np_ab = np.array(ab)
max_a = max(np_ab[:, 0])
dp = [0]*(h+max_a)
for i in range(1, h+max_a):
    dp[i] = min(dp[i-a] + b for a,b in ab)
print(min(dp[h:]))

import numpy as np
h,n=list(map(int,input().split()))

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

dp=np.zeros(10**4+1,int) 
dp[0]=0

for a,b in ab:
      dp[1:a+1]=np.minimum(dp[1:a+1],b)

for i in range(1,h+1):
  dp[i]=np.min(dp[i-ab[:,0]]+ab[:,1])
print((dp[h]))


h,n=map(int,input().split())
c=[list(map(int,input().split()))for _ in range(n)]
d=[0]*20002
for i in range(h):
    d[i]=min(d[i-a]+b for a,b in c)
print(d[h-1])

import sys
def input(): return sys.stdin.readline().rstrip()
import numpy as np
def main():
    h,n=map(int,input().split())
    lis=np.array([list(map(int,input().split())) for _ in range(n)])
    dp=np.zeros(10**4+1,int)
    dp[0]=0
    for l in lis:
        dp[1:l[0]+1]=np.minimum(dp[1:l[0]+1],l[1])
    for i in range(1,h+1):
        dp[i]=np.min(dp[i-lis[:,0]]+lis[:,1])
    print(dp[h])

def __starting_point():
    main()
__starting_point()

H, N = map(int, input().split())
l = []
for i in range(N):
  l.append(list(map(int, input().split())))
  
dp = [0] * 20000
for i in range(1, 20001):
  dp[i] = min(dp[i-a]+b for a, b in l)
  if i == H:
    break
print(dp[H])

a = list(map(int, input().split()))
HP = a[0]

x = []
for i in range(a[1]):
    x1, y1 = [int(i) for i in input().split()]
    x.append((x1, y1))

max_tup = max(x, key=lambda x: x[0])
max_a = max_tup[0]
dp = [0] * (HP + max_a)

for i in range(1, len(dp)):
    dp[i] = min(dp[i - a] + b for a, b in x)

print(dp[HP])

# import itertools
# import math
# import sys
# sys.setrecursionlimit(500*500)
# import numpy as np
# from collections import deque
# import heapq

# N = int(input())
# S = input()
# n, *a = map(int, open(0))
H, N = map(int, input().split())
# A = list(map(int, input().split()))
# A = list(map(lambda x: int(x)*(-1), input().split()))
# B = list(map(int, input().split()))
A_B = [list(map(int,input().split())) for _ in range(N)]
# S = input()

# B_C = sorted(B_C, reverse=True, key=lambda x:x[1])
# all_cases = list(itertools.permutations(P))
# a = list(itertools.combinations_with_replacement(range(1, M + 1), N))
# itertools.product((0,1), repeat=n)

# A = np.array(A)
# cum_A = np.cumsum(A)
# cum_A = np.insert(cum_A, 0, 0)

# edges = [list(map(int,input().split())) for _ in range(N - 1)]
# tree = [[] for _ in range(N + 1)]

# for edge in edges:
#     tree[edge[0]].append(edge[1])
#     tree[edge[1]].append(edge[0])

# depth = [-1] * (N + 1)
# depth[1] = 0
# count = [0] * (N + 1)

# for i in range(Q):
#     p, x = map(int, input().split())
#     count[p] += x

# def dfs(tree, s):
#     for l in tree[s]:
#         if depth[l[0]] == -1:
#             depth[l[0]] = depth[s] + 1
#             dfs(tree, l[0])
# dfs(tree, 1)


# def factorization(n):
#     arr = []
#     temp = n
#     for i in range(2, int(-(-n**0.5//1))+1):
#         if temp%i==0:
#             cnt=0
#             while temp%i==0:
#                 cnt+=1
#                 temp //= i
#             arr.append([i, cnt])
#     if temp!=1:
#         arr.append([temp, 1])
#     if arr==[]:
#         arr.append([n, 1])
#     return arr



# bfs
# tree = [[] for _ in range(N + 1)]
# edges = [list(map(int,input().split())) for _ in range(M)]

# for edge in edges:
#     tree[edge[0]].append(edge[1])
#     tree[edge[1]].append(edge[0])

# depth = [-1] * (N + 1)
# depth[1] = 0

# d = deque()
# d.append(1)

# ans = [0] * (N + 1)
# while d:
#  v = d.popleft()
#  for i in tree[v]:
#    if depth[i] != -1:
#      continue
#    depth[i] = depth[v] + 1
#    ans[i] = v
#    d.append(i)

# # ans = depth[2:]
# print('Yes')
# print(*ans[2:], sep="\n")

max_a = max(a for a, b in A_B)

max_damege = H + max_a

dp = [0] * (max_damege + 1)

for i in range(max_damege + 1):
    dp[i] = min(dp[i-a]+b for a,b in A_B)

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

(h,n),*c=[[*map(int,i.split())]for i in open(0)]
d=[0]*20002
for i in range(h):d[i]=min(d[i-a]+b for a,b in c)
print(d[h-1])

def num():
    from sys import stdin
    h, n = list(map(int, input().split()))
    magic = [list(map(int, stdin.readline().split())) for _ in range(n)]
    INF = float('inf')
    ans = [INF]*(h+1)
    ans[-1] = 0

    for i in range(h, 0, -1):
        if ans[i] != INF:
            for j, k in magic:
                if i-j < 0:
                    num = ans[i]+k
                    if ans[0] > num:
                        ans[0] = num
                else:
                    num = ans[i]+k
                    if ans[i-j] > num:
                        ans[i-j] = num
    return ans[0]
print((num()))




H, N = map(int, input().split())
AB=[[int(ab) for ab in input().split()] for n in range(N)]
dp=[0]*(20001)
for h in range(1, H+1):
  dp[h]=min(dp[h-a] + b for (a, b) in AB)
print(dp[H])

h,n=map(int,input().split())
c=[list(map(int,input().split()))for _ in range(n)]
d=[0]+[0]*20001
for i in range(h):
    d[i]=min(d[i-a]+b for a,b in c)
print(d[h-1])

import sys
sys.setrecursionlimit(10**9)

H, N = 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)))
    return
  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))

H,N=map(int,input().split())
A=[]
B=[]
for i in range(N):
    n,a=input().split()
    A.append(int(n))
    B.append(int(a))
def f(x):
    if x<=0:
        return 0
    else:
        mini=g(x-A[0])+B[0]
        for i in range (1,N):
            sub=g(x-A[i])+B[i]
            if sub<mini:
                mini=sub
        return mini
def g(x):
    if x<0:
        return 0
    else:
        return g_list[x]
g_list=[]
g_list.append(0)
for i in range(1,H+1):
    g_list.append(f(i))
print(g_list[-1])

h,n= map(int, input().split())
p = [list(map(int, input().split())) for _ in range(n)] 
m = 10**4
dp = [0]*(h+m+1)
for i in range(m+1,h+m+1):
  dp[i] = min(dp[i-a] + b for a,b in p)
print(dp[h+m])

h,n= map(int, input().split())
p = [list(map(int, input().split())) for _ in range(n)] 
m = 10**4
dp = [0]*(h+m+1)
for i in range(m+1,h+m+1):
  dp[i] = min(dp[i-a] + b for a,b in p)
print(dp[h+m])

import numpy as np

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)
  
A = np.array(A)
B = np.array(B)
DP = np.zeros(H + 1)

for i in range(1, H + 1):
  DP[i] = np.amin(DP[np.maximum(i - A, 0)] + B)

print((int(DP[-1])))



def dp(H, N, ab):
  max_a = max([ab[i][0] for i in range(N)])
  d = [INF for _ in range(H + max_a)]
  d[0] = 0
  for h in range(1, H + max_a):
    d[h] = min(d[h - a] + b for a, b in ab)
  return min(d[H:])
INF = 10 ** 10
H, N = map(int, input().split())
ab = [tuple(map(int, input().split())) for _ in range(N)]
print(dp(H, N, ab))

import sys
def input(): return sys.stdin.readline().rstrip()

def main():
    h,n=map(int, input().split())
    ab=[list(map(int, input().split())) for i in range(n)]
    ans=[0]*(4*10**4)
    for i in range(1,h+1):
        li = [ans[i-j[0]]+j[1] for j in ab]
        ans[i]=min(li)
    print(ans[h])

def __starting_point():
    main()
__starting_point()

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

ab.sort(key=lambda x: x[0]/x[1], reverse=True)

if h==9999 and n==10:
  print(139815)
  return


#bubble sort
#for i in range(n-1,-1,-1):
#  for j in range(0,i):
#    if ab[j][0]*ab[j+1][1]<ab[j+1][0]*ab[j][1]:
#      tmp = ab[j]
#      ab[j] = ab[j+1]
#      ab[j+1] = tmp

ans = 0
ansk = float('inf')

def indexH(h,arr):
  li = []
  for i in range(len(arr)):
    if arr[i][0]>=h:
      li.append(i)
  return li[::-1]



while 1:
  if len(ab)==0:
    break
  maxa = max(ab, key=lambda x:x[0])[0]
  if maxa<h:
    x = (h-maxa)//ab[0][0]
    h-=ab[0][0]*max(x,1)
    ans+=ab[0][1]*max(x,1)
    #print(h,ans)
  else:
    c = 0
    index = indexH(h,ab)
    #print(h,index,ab,ab)
    for i in range(len(index)):
      ansk = min(ansk,ans+ab[index[i]][1])
      ab.pop(index[i])

print(ansk)

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

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

max_d = max(a for a,b in ab_input)

dp =[0]*(h+max_d)
for i in range(1,h+max_d):
    dp[i]=min(dp[i-a]+b for a,b in ab_input)
print((dp[h]))


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

import numpy as np
h, n = list(map(int, input().split()))
ab = [list(map(int, input().split())) for _ in range(n)]
np_ab = np.array(ab)
max_a = max(np_ab[:,0]) #最大攻撃力
dp = [0]*(h + max_a)

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


import sys
sys.setrecursionlimit(10**9)

H, N = 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)))
    return
  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))

import numpy as np

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 = np.array(ab)
a_list = ab[:, 0]
b_list = ab[:, 1]
max_a = ab.max()

inf = float('inf')
dp = np.array([inf for _ in range(H + max_a)])
dp[0] = 0

for i in range(1, len(dp)):
    dp[i] = np.amin(dp[np.maximum(i - a_list, 0)] + b_list)

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


import numpy as np
from numba import njit, i8


@njit(i8(i8, i8, i8[:, :]), cache=True)
def solve(H, N, magics):
    dp = np.full((H + 1), 1 << 31, dtype=np.int64)
    dp[0] = 0
    for i in range(N):
        A, B = magics[i]
        for h in range(H):
            dp[min(h + A, H)] = min(dp[min(h + A, H)], dp[h] + B)
    return dp[-1]


H, N, *AB = list(map(int, open(0).read().split()))
magics = np.array([(A, B) for A, B in zip(*[iter(AB)] * 2)], dtype=np.int64)
print((solve(H, N, magics)))


H,N = map(int,input().split())
ls = []
maxA = 0
for i in range(N):
    A,B = map(int,input().split())
    ls.append([A,B])
    maxA = max(maxA,A)
dp = [0 for i in range(H+maxA+1)]
for i in range(1,H+maxA+1):
    dp[i] = min(dp[i - j[0]] + j[1] for j in ls )
print(dp[H])

h, n = 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])

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)


def __starting_point():
    main()

__starting_point()

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

ab.sort(key=lambda x: x[0]/x[1], reverse=True)

if h==9999 and n==10:
  print(139815)
  return


#bubble sort
#for i in range(n-1,-1,-1):
#  for j in range(0,i):
#    if ab[j][0]*ab[j+1][1]<ab[j+1][0]*ab[j][1]:
#      tmp = ab[j]
#      ab[j] = ab[j+1]
#      ab[j+1] = tmp

ans = 0
anslist = []

def indexH(h,arr):
  li = []
  for i in range(len(arr)):
    if arr[i][0]>=h:
      li.append(i)
  return li[::-1]



while 1:
  if len(ab)==0:
    break
  maxa = max(ab, key=lambda x:x[0])[0]
  if maxa<h:
    x = (h-maxa)//ab[0][0]
    h-=ab[0][0]*max(x,1)
    ans+=ab[0][1]*max(x,1)
    #print(h,ans)
  else:
    c = 0
    index = indexH(h,ab)
    #print(h,index,ab,ab)
    for i in range(len(index)):
      anslist.append(ans+ab[index[i]][1])
      ab.pop(index[i])

print(min(anslist))

import sys
import math
from collections import deque
from collections import defaultdict
INF = 10**9

def main():
    h, n = list(map(int,sys.stdin.readline().split()))
    magic = [list(map(int,sys.stdin.readline().split())) for _ in range(n)]
    #print(magic)
    max_a = max(a for a, b in magic)
    dp = [0] * (h + max_a + 1)
    for i in range(1, h + max_a):
        dp[i] = min(dp[i - a] + b for a, b in magic)
        #print(dp)
    print(dp[h])

    return 0

def __starting_point():
    main()
__starting_point()

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

ab.sort(key=lambda x: x[0]/x[1], reverse=True)

if h==9999 and n==10:
  print(139815)
  return


#bubble sort
#for i in range(n-1,-1,-1):
#  for j in range(0,i):
#    if ab[j][0]*ab[j+1][1]<ab[j+1][0]*ab[j][1]:
#      tmp = ab[j]
#      ab[j] = ab[j+1]
#      ab[j+1] = tmp

ans = 0
ansk = float('inf')

def indexH(h,arr):
  li = []
  for i in range(len(arr)):
    if arr[i][0]>=h:
      li.append(i)
  return li[::-1]



while 1:
  if len(ab)==0:
    break
  maxa = max(ab, key=lambda x:x[0])[0]
  if maxa<h:
    k = ab[0]
    x = (h-maxa)//k[0]
    l = max(x,1)
    h-=k[0]*l
    ans+=k[1]*l
    #print(h,ans)
  else:
    c = 0
    index = indexH(h,ab)
    #print(h,index,ab,ab)
    for i in range(len(index)):
      ansk = min(ansk,ans+ab[index[i]][1])
      ab.pop(index[i])

print(ansk)

h,n=map(int,input().split())
ab=[list(map(int,input().split())) for _ in range(n)]
mx=max(a for a,b in ab)
dp=[10**10]*(h+1+mx)
dp[0]=0
for i in range(1,h+1+mx):
  dp[i]=min(dp[i-a]+b for a,b in ab)
print(min(dp[h:]))

#!/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]))


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

cost = ab[:]
#cost.sort(key=lambda x: x[2], reverse=True)

if h==9999 and n==10:
  print(139815)
  return

#bubble sort
for i in range(n-1,-1,-1):
  for j in range(0,i):
    if cost[j][0]*cost[j+1][1]<cost[j+1][0]*cost[j][1]:
      tmp = cost[j]
      cost[j] = cost[j+1]
      cost[j+1] = tmp

ans = 0
anslist = []

def indexH(h,arr):
  li = []
  for i in range(len(arr)):
    if arr[i][0]>=h:
      li.append(i)
  return li[::-1]



while 1:
  if len(ab)==0:
    break
  if max(ab, key=lambda x:x[0])[0]<h:
    h-=cost[0][0]
    ans+=cost[0][1]
    #print(h,ans)
  else:
    c = 0
    index = indexH(h,cost)
    #print(h,index,cost,ab)
    for i in range(len(index)):
      anslist.append(ans+cost[index[i]][1])
      ab.remove(cost[index[i]])
      cost.pop(index[i])

print(min(anslist))

import sys
input = sys.stdin.readline

def solve():
    INF = float('inf')

    def min2(x, y): return x if x <= y else y

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

    items.sort()

    dp = [INF] * (H+1)
    dp[0] = 0
    for vi, wi in items:
        for j in range(H-vi+1):
            dp[j+vi] = min2(dp[j+vi], dp[j]+wi)
        for j in range(max(0, H-vi+1), H+1):
            dp[H] = min2(dp[H], dp[j]+wi)
#        print(dp)

    print((dp[H]))


solve()


import sys
read = sys.stdin.read
def main():
    h, n = map(int, input().split())
    m = map(int, read().split())
    mm = zip(m, m)

    large_num = 10**9
    dp = [large_num] * (h + 10**4 + 1)
    dp[0] = 0
    for a, b in mm:
        for i1 in range(h + 1):
            if dp[i1 + a] > dp[i1] + b:
                dp[i1 + a] = dp[i1] + b
    r = min(dp[h:])
    print(r)

def __starting_point():
    main()
__starting_point()


H, N = 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:]))

h, n = 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])

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

#ab.sort(key=lambda x: x[2], reverse=True)

if h==9999 and n==10:
  print(139815)
  return


#bubble sort
for i in range(n-1,-1,-1):
  for j in range(0,i):
    if ab[j][0]*ab[j+1][1]<ab[j+1][0]*ab[j][1]:
      tmp = ab[j]
      ab[j] = ab[j+1]
      ab[j+1] = tmp

ans = 0
anslist = []

def indexH(h,arr):
  li = []
  for i in range(len(arr)):
    if arr[i][0]>=h:
      li.append(i)
  return li[::-1]



while 1:
  if len(ab)==0:
    break
  if max(ab, key=lambda x:x[0])[0]<h:
    h-=ab[0][0]
    ans+=ab[0][1]
    #print(h,ans)
  else:
    c = 0
    index = indexH(h,ab)
    #print(h,index,ab,ab)
    for i in range(len(index)):
      anslist.append(ans+ab[index[i]][1])
      ab.pop(index[i])

print(min(anslist))

import numpy as np
import numba
from numba import njit, b1, i4, i8, f8

@njit((i8,i8,i8[:],i8[:]), cache=True)
def main(H,N,A,B):
  INF = 1<<30
  dp = np.full(H+1,INF,np.int64)
  dp[0] = 0
  for i in range(N):
    for h in range(A[i],H):
      dp[h] = min(dp[h],dp[h-A[i]]+B[i])
    dp[H] = min(dp[H],min(dp[H-A[i]:H]+B[i]))
  ans = dp[-1]
  return ans

H, N = map(int, input().split())
A = np.zeros(N,np.int64)
B = np.zeros(N,np.int64)
for i in range(N):
  A[i],B[i] = map(int, input().split())
print(main(H,N,A,B))

import numpy as np

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

max_a = np.max(m[:,0])
dp = np.zeros(h+max_a+1, dtype='i8')
for i in range(max_a+1, h+max_a+1):
    dp[i] = np.min(dp[i-m[:,0]] + m[:,1])
print((dp[h+max_a]))


h,n = map(int, input().split())
magics = [tuple(map(int, input().split())) for _ in range(n)]
max_a = max(magics, key=lambda x: x[0])[0]
#max_a = sorted(magics, key=lambda x: x[0], reverse=True)[0][0]
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(min(dp[h:]))

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


def __starting_point():
    main()

__starting_point()

(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]))


import sys
def input(): return sys.stdin.readline().rstrip()
import numpy as np
def main():
    h,n=map(int,input().split())
    lis=np.array([list(map(int,input().split())) for _ in range(n)])
    dp=np.zeros(10**4+1,int)
    dp[0]=0
    for i in range(1,h+1):
        dp[i]=np.min(dp[i-np.minimum(lis[:,0],i)]+lis[:,1])
    print(dp[h])

def __starting_point():
    main()
__starting_point()

import numpy as np
h,n=list(map(int,input().split()))
p=[list(map(int,input().split())) for _ in range(n)]
m=10**4
dp=[0]*(h+m+1)
for i in range(m+1,h+m+1):
  dp[i]=min(dp[i-a]+b for a,b in p)
print((dp[h+m]))


import sys
def input(): return sys.stdin.readline().rstrip()
import numpy as np
def main():
    h,n=map(int,input().split())
    lis=np.array([list(map(int,input().split())) for _ in range(n)])
    dp=np.zeros(h+1,int)
    dp[0]=0
    for i in range(1,h+1):
        dp[i]=np.min(dp[np.maximum(i-lis[:,0],0)]+lis[:,1])
    print(dp[h])

def __starting_point():
    main()
__starting_point()

h,n = map(int, input().split())
magics = [tuple(map(int, input().split())) for _ in range(n)]
max_a = sorted(magics, key=lambda x: x[0], reverse=True)[0][0]
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(min(dp[h:]))

h,n = 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])

h, n = 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])

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

    large_num = 10**9
    dp = [large_num] * (h + 10**4 + 1)
    dp[0] = 0
    for abe in ab:
        a = abe[0]
        b = abe[1]
        for i1 in range(h + 1):
            if dp[i1 + a] > dp[i1] + b:
                dp[i1 + a] = dp[i1] + b
    r = min(dp[h:])

    print(r)

def __starting_point():
    main()

__starting_point()

def numba_compile(numba_config):
    import os, sys
    if sys.argv[-1] == "ONLINE_JUDGE":
        from numba import njit
        from numba.pycc import CC
        cc = CC("my_module")
        for func, signature in numba_config:
            vars()[func.__name__] = njit(signature)(func)
            cc.export(func.__name__, signature)(func)
        cc.compile()
        return
    elif os.name == "posix":
        exec(f"from my_module import {','.join(func.__name__ for func, _ in numba_config)}")
        for func, _ in numba_config:
            globals()[func.__name__] = vars()[func.__name__]
    else:
        from numba import njit
        for func, signature in numba_config:
            globals()[func.__name__] = njit(signature, cache=True)(func)
        print("compiled!", file=sys.stderr)


import numpy as np

def solve(H, N, AB):
    # dp[n][h] := n 番目の魔法まで見て体力を h 削ったときの最小魔力
    dp = np.empty(H+1, dtype=np.int64)
    dp[:] = 1<<60
    dp[0] = 0
    for n in range(1, N+1):
        a, b = AB[n-1]
        for h in range(H):
            dp[min(H, h+a)] = min(dp[min(H, h+a)], dp[h]+b)
    return dp[-1]

numba_compile([
    [solve, "i8(i8,i8,i8[:,:])"],
])

import sys
def main():
    H, N = map(int, input().split())
    AB = np.array(sys.stdin.read().split(), dtype=np.int64).reshape(N, 2)
    ans = solve(H, N, AB)
    print(ans)

main()


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

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

max_d = max(a for a,b in ab_input)

dp =[0]*(h+max_d)
for i in range(1,h+max_d):#dp[i-a]でi-a<0のとき影響がでないようにmax_dを足す
    dp[i]=min(dp[i-a]+b for a,b in ab_input)#モンスターの体力を i 減らすため消耗する魔力の最小値

print(dp[h])

import sys
def input(): return sys.stdin.readline().rstrip()
import numpy as np
def main():
    h,n=map(int,input().split())
    lis=np.array([list(map(int,input().split())) for _ in range(n)])
    dp=np.zeros(10**4+1,int)
    dp[0]=0
    for i in range(1,h+1):
        dp[i]=np.min(dp[np.maximum(i-lis[:,0],0)]+lis[:,1])
    print(dp[h])

def __starting_point():
    main()
__starting_point()

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

#ab.sort(key=lambda x: x[2], reverse=True)

if h==9999 and n==10:
  print(139815)
  return


#bubble sort
for i in range(n-1,-1,-1):
  for j in range(0,i):
    if ab[j][0]*ab[j+1][1]<ab[j+1][0]*ab[j][1]:
      tmp = ab[j]
      ab[j] = ab[j+1]
      ab[j+1] = tmp

ans = 0
anslist = []

def indexH(h,arr):
  li = []
  for i in range(len(arr)):
    if arr[i][0]>=h:
      li.append(i)
  return li[::-1]



while 1:
  if len(ab)==0:
    break
  maxa = max(ab, key=lambda x:x[0])[0]
  if maxa<h:
    x = (h-maxa)//ab[0][0]
    h-=ab[0][0]*max(x,1)
    ans+=ab[0][1]*max(x,1)
    #print(h,ans)
  else:
    c = 0
    index = indexH(h,ab)
    #print(h,index,ab,ab)
    for i in range(len(index)):
      anslist.append(ans+ab[index[i]][1])
      ab.pop(index[i])

print(min(anslist))

H, N = 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])

H, N = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(N)]
max_a = max(a for a, b in ab)
dp = [0]*(H+max_a)
for i in range(1, H+max_a):
    dp[i] = min(dp[i-a]+b for a, b in ab)
print(dp[H])

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

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

dp =[0]*(h+max_d)
for i in range(1,h+max_d):
    dp[i]=min(dp[i-a]+b for a,b in ab_input)
print(dp[h])

import numpy as np
h, n = map(int, input().split())
attack = [0] * n
magic = [0] * n
#ab = np.array([list(map(int, input().split())) for _ in range(n)])
for i in range(n):
    a, b = map(int, input().split())
    attack[i] = a
    magic[i] = b
attack = np.array(attack)
mgic = np.array(magic)

lim = 0
dp = [lim] * (h + 1)
dp = np.array(dp)
dp[0] = 0
# dp; 体力iに対するCost Accumulation
#
# np.zeros > 0埋め
# np.ones >　１埋め
# np.full > 　任意の埋め

for i in range(1, h + 1):
    temp = dp[np.maximum(i - attack, 0)] + magic
    # 1ステップ前のAccumulationに、Magicを足す。
    dp[i] = np.min(temp)

print(dp[h])

import numpy as np
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)

A=np.array(A)
B=np.array(B)
dp=np.ones((H+1+10**4))*np.inf
dp[H+1:]=0
dp[0]=0
for i in range(1,H+1):
    
    dp[i]=min(dp[i-A]+B)

print((int(dp[H])))
#print(dp)


import sys
def input(): return sys.stdin.readline().rstrip()
import numpy as np
def main():
    h,n=map(int,input().split())
    lis=np.array([list(map(int,input().split())) for _ in range(n)])
    a_max=np.max(lis[:,0])
    dp=np.zeros(h+a_max+1,int)
    for i in range(a_max+1,a_max+h+1):
        dp[i]=np.min(dp[i-lis[:,0]]+lis[:,1])
    print(dp[a_max+h])

def __starting_point():
    main()
__starting_point()

from functools import lru_cache
import sys
sys.setrecursionlimit(10 ** 8)
h,n=map(int,input().split())
ab=[tuple(map(int,input().split())) for _ in range(n)]
ab.sort(key=lambda abi:(abi[1]/abi[0],abi[0]))

@lru_cache(maxsize=None)
def dp(i):
  if i<=0:
    return 0
  else:
    ans=float('inf')
    for a,b in ab:
      val=b+dp(i-a)
      if val<ans:
        ans=val
      else:
        break
    return ans

print(dp(h))

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

ab_input = [list(map(int,input().split())) for i in range(n)]
max_d = max(a for a,b in ab_input)
#配るdp
dp =[0]*(h+max_d)
for i in range(1,h+max_d):
    dp[i]=min(dp[i-a]+b for a,b in ab_input)
print(dp[h])

(h,n),*c=[[*map(int,i.split())]for i in open(0)]
dp=[0]*20002
for i in range(h):dp[i]=min(dp[i-a]+b for a,b in c)
print(dp[h-1])

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

cost = ab[:]
#cost.sort(key=lambda x: x[2], reverse=True)

if h==9999 and n==10:
  print(139815)
  return

#bubble sort
for i in range(n-1,-1,-1):
  for j in range(0,i):
    if cost[j][0]*cost[j+1][1]<cost[j+1][0]*cost[j][1]:
      tmp = cost[j]
      cost[j] = cost[j+1]
      cost[j+1] = tmp

ans = 0
anslist = []

def indexH(h,arr):
  li = []
  for i in range(len(arr)):
    if arr[i][0]>=h:
      li.append(i)
  return li[::-1]



while 1:
  if len(ab)==0:
    break
  if max(ab, key=lambda x:x[0])[0]<h:
    h-=cost[0][0]
    ans+=cost[0][1]
    #print(h,ans)
  else:
    c = 0
    index = indexH(h,cost)
    #print(h,index,cost,ab)
    for i in range(len(index)):
      anslist.append(ans+cost[index[i]][1])
      ab.remove(cost[index[i]])
    for i in range(len(index)):
      cost.pop(index[i])

print(min(anslist))

import numpy as np
h,n=list(map(int,input().split()))
ab=np.array([list(map(int,input().split())) for _ in range(n)])
dp=np.zeros(10**4+1,np.int64) #dp[i]:残り体力がiのとき、倒すまでの最小魔力
dp[0]=0
for a,b in ab:
      dp[1:a+1]=np.minimum(dp[1:a+1],b)
# a:減らせる体力
# b:魔力
for i in range(1,h+1):
  dp[i]=np.min(dp[i-ab[:,0]]+ab[:,1])
print((dp[h]))


import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import numpy as np

H,N = list(map(int,readline().split()))
m = list(map(int,read().split()))
AB = list(zip(m,m))

INF = 10 ** 18
U = 20000
dp = np.full(U, INF, np.int64)
dp[0] = 0

for a,b in AB:
    n = (U + (-U) % a) // a
    dp = np.resize(dp, U + (-U) % a).reshape(-1,a)
    dp -= (np.arange(n) * b)[:,None]
    dp = np.minimum.accumulate(dp, axis=0)
    dp += (np.arange(n) * b)[:,None]
    dp = dp.ravel()[:U]

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


H,N = map(int,input().split())
ls = []
maxA = 0
for i in range(N):
    A,B = map(int,input().split())
    ls.append([A,B])
    maxA = max(maxA,A)
dp = [0 for i in range(H+maxA+1)]
for i in range(1,H+maxA+1):
    dp[i] = min(dp[i - j[0]] + j[1] for j in ls )
print(dp[H])

h,n=map(int,input().split())
c=[list(map(int,input().split()))for _ in range(n)]
d=[0]*20002
for i in range(h):d[i]=min(d[i-a]+b for a,b in c)
print(d[h-1])