module app;

import core.bitop;

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

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;
        }
	}
}

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

    for (int hp = 1; hp <= input.h; hp++)
    {
        foreach (m; input.m)
        {
            auto prevMp = m.a > hp ? 0 : dp[hp - m.a];
            auto newMp = prevMp + m.b;
            if (newMp < dp[hp])
                dp[hp] = newMp;
        }
    }

	return dp[input.h];
}

alias retType = ReturnType!main2;
static if (!is(retType == void))
{
	unittest { writeln("begin unittest"); }
	auto _placeholder_ = ReturnType!main2.init;

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

	unittest // example2
	{
		string example =
`100 6
1 1
2 3
3 9
4 27
5 81
6 243`;
		if (example.empty) return;
		Input input = void;
		parseExample(input, example);
		auto result = main2(&input);
		printResult(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`;
		if (example.empty) return;
		Input input = void;
		parseExample(input, example);
		auto result = main2(&input);
		printResult(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 printResult(T)(T result)
{
	static if (isFloatingPoint!T) writefln("%f", result);
	else writeln(result);
}

void main()
{
	Input input = void;
	parseInput(input, stdin);
	alias retType = ReturnType!main2;
	static if (is(retType == void))
		main2(&input);
	else
	{
		auto result = main2(&input);
		printResult(result);
	}
}
