unittest
{
	assert( [ "9 3", "8 3", "4 2", "2 1" ].parse.expand.solve == 4 );
	assert( [ "100 6", "1 1", "2 3", "3 9", "4 27", "5 81", "6 243" ].parse.expand.solve == 100 );
	assert( [ "9999 10", "540 7550", "691 9680", "700 9790", "510 7150", "415 5818", "551 7712", "587 8227", "619 8671", "588 8228", "176 2461" ].parse.expand.solve == 139815 );
}



import std.algorithm;
import std.conv;
import std.range;
import std.stdio;
import std.typecons;

void main()
{
	stdin.byLineCopy.parse.expand.solve.writeln;
}

auto parse( Range )( Range input )
if( isInputRange!Range && is( ElementType!Range == string ) )
{
	auto hn = input.front.split.to!( long[] );
	auto abs = new long[ 2 ][ hn[ 1 ] ];
	foreach( ref ab; abs )
	{
		input.popFront;
		ab = input.front.split.to!( long[] );
	}
	return tuple( hn[ 0 ], abs );
}

auto solve( long h, long[ 2 ][] abs )
{
	// dp[ 与ダメージ合計 ] = 使用魔力合計
	auto ans = long.max;
	auto dp = new long[ 1 + h + 10L ^^ 4 ];
	dp[ 1 .. $ ] = long.max;
	foreach( d; 0L .. h )
	{
		foreach( ab; abs )
		{
			if( dp[ d ] == long.max ) continue;
			
			auto dd = d + ab[ 0 ];
			dp[ dd ] = min( dp[ dd ], dp[ d ] + ab[ 1 ] );
			if( h <= dd ) ans = min( ans, dp[ dd ] );
		}
	}
	return ans;
}
