void main()
{
    long[] tmp = rdRow;
    long h = tmp[0], n = tmp[1];
    long[] a = new long[n], b = new long[n];
    foreach (i; 0 .. n)
    {
        tmp = rdRow;
        a[i] = tmp[0], b[i] = tmp[1];
    }

    long inf = 1L << 60;
    long[] dp = new long[](h+1);
    dp[] = inf;
    dp[0] = 0;
    foreach (i; 0 .. n)
    {
        long cnt = h / a[i];
        foreach (j; 0 .. cnt)
        {
            dp[j+1] = min(dp[j+1], b[i]*(j+1));
        }
        foreach (j; 0 .. h)
        {
            if (dp[j] != inf)
            {
                long k = j + a[i];
                if (k <= h)
                {
                    dp[k] = min(dp[k], dp[j]+b[i]);
                }
            }
            long rem = h - j;
            long num = (rem + a[i] - 1) / a[i];
            dp[h] = min(dp[h], b[i]*num+dp[j]);
        }
    }

    dp[h].writeln;
}

T rdElem(T = long)()
if (!is(T == struct))
{
    return readln.chomp.to!T;
}

alias rdStr = rdElem!string;
alias rdDchar = rdElem!(dchar[]);

T rdElem(T)()
if (is(T == struct))
{
    T result;
    string[] input = rdRow!string;
    assert(T.tupleof.length == input.length);
    foreach (i, ref x; result.tupleof)
    {
        x = input[i].to!(typeof(x));
    }
    return result;
}

T[] rdRow(T = long)()
{
    return readln.split.to!(T[]);
}

T[] rdCol(T = long)(long col)
{
    return iota(col).map!(x => rdElem!T).array;
}

T[][] rdMat(T = long)(long col)
{
    return iota(col).map!(x => rdRow!T).array;
}

void wrMat(T = long)(T[][] mat)
{
    foreach (row; mat)
    {
        foreach (j, compo; row)
        {
            compo.write;
            if (j == row.length - 1) writeln;
            else " ".write;
        }
    }
}

import std.stdio;
import std.string;
import std.array;
import std.conv;
import std.algorithm;
import std.range;
import std.math;
import std.numeric;
import std.traits;
import std.container;
import std.functional;
import std.typecons;
import std.ascii;
import std.uni;