import std.stdio, std.string, std.algorithm, std.array, std.range, std.conv,
    std.typecons, std.math, std.container, std.format, std.numeric;

alias T = Tuple!(long, long);
void main(string[] args)
{
    long h, n;
    readf("%d %d\n", &h, &n);

    auto as = new long[](n);
    auto bs = new long[](n);

    foreach (i; 0 .. n)
    {
        long a, b;
        readf("%d %d\n", &a, &b);
        as[i] = a;
        bs[i] = b;
    }
    long maxa = maxElement(as);

    long[] hs = new long[](h + maxa + 1);
    foreach (i; 0 .. hs.length)
    {
        hs[i] = long.max / 10;
    }
    hs[0] = 0;
    foreach (i; 0 .. h + 1)
    {
        foreach (j; 0 .. n)
        {
            hs[i + as[j]] = min(hs[i + as[j]], hs[i] + bs[j]);
        }
    }
    writeln(hs[h .. $].minElement);
}
