local h,n=io.read("n","n")
local a,b={},{}
for i=1,n do
    a[i],b[i]=io.read("n","n")
end

local dp={0}
for i=2,h+1 do
    dp[i]=10^9
end

for i=1,n do
    for j=1,h+1 do
        local k=math.min(j+a[i],h+1)
        dp[k]=math.min(dp[k],dp[j]+b[i])
    end
end
print(dp[h+1])