local mce, mma, mmi = math.ceil, math.max, math.min
local h, n = io.read("*n", "*n")
local inf = 1000000007
local z = {}
for i = 1, 10000 do
  z[i] = inf
end
for i = 1, n do
  local a, b = io.read("*n", "*n")
  z[a] = mmi(z[a], b)
end
local t = {}
for i = 1, h do
  t[i] = inf
end
for a = 1, 10000 do
  local b = z[a]
  if b < inf then
    for src = h - 1, 1, -1 do
      local lim = mce((h - src) / a)
      for j = 1, lim do
        local dst = mmi(h, src + a * j)
        t[dst] = mmi(t[dst], t[src] + b * j)
      end
    end
    do -- src = 0
      local lim = mce(h / a)
      for j = 1, lim do
        local dst = mmi(h, a * j)
        t[dst] = mmi(t[dst], b * j)
      end
    end
  end
end
print(t[h])
