module app;

import core.bitop;

import std.algorithm;
import std.array;
import std.bigint;
import std.conv;
import std.stdio;
import std.string;

struct Magic
{
    int a;
    int b;
}

struct Input
{
	int h;
	int n;
    Magic[] m;
}

void parseInput(T)(out Input input, T file)
{
	with (file) with (input)
	{
		auto hn = readln().strip().split();
		h = hn[0].to!int;
		n = hn[1].to!int;

        foreach (i; 0..n)
        {
            auto ab = readln().strip().split().map!(to!int).array;
            Magic temp;
            temp.a = ab[0];
            temp.b = ab[1];
            m ~= temp;
        }
	}
}

struct Output
{
}


auto main2(Input* input)
{
    auto dp = new int[10000*10000+1];

    input.m.sort!((m1, m2) => m1.b < m2.b);

    LOOP_DP:
    for (int limMp = 1; limMp < dp.length; limMp++)
    {
        foreach (m; input.m)
        {
            auto mp = m.b;

            if (mp > limMp)
                continue LOOP_DP;

            if (dp[limMp] < dp[limMp - mp] + m.a)
                dp[limMp] = dp[limMp - mp] + m.a;

            if (dp[limMp] >= input.h)
                return limMp;
        }
    }

	assert(0);
}

unittest { writeln("begin unittest"); }

unittest // example1
{
	string example =
`9 3
8 3
4 2
2 1`;
	Input input = void;
	parseExample(input, example);
	auto result = main2(&input);
	writeln(result);
	assert(result == 4);
}

unittest // example2
{
	string example =
`100 6
1 1
2 3
3 9
4 27
5 81
6 243`;
	Input input = void;
	parseExample(input, example);
	auto result = main2(&input);
	writeln(result);
	assert(result == 100);
}

unittest // example3
{
	string example =
`9999 10
540 7550
691 9680
700 9790
510 7150
415 5818
551 7712
587 8227
619 8671
588 8228
176 2461`;
	Input input = void;
	parseExample(input, example);
	auto result = main2(&input);
	writeln(result);
	assert(result == 139815);
}

unittest { writeln("end unittest"); }

void parseExample(out Input input, string example)
{
	struct Adapter
	{
		string[] _lines;
		this(string input) { _lines = input.splitLines(); }
		string readln() { auto line = _lines[0]; _lines = _lines[1..$]; return line; }
	}
	parseInput(input, Adapter(example));
}

void main()
{
	Input input = void;
	parseInput(input, stdin);
	auto result = main2(&input);
	writeln(result);
}
