module E;

import std.stdio;
import std.conv;
import std.string;
import std.typecons;
import std.algorithm;
import std.array;
import std.range;
import std.math;
import std.regex : regex;
import std.container;
import std.bigint;


void main()
{
  int h, n;
  readf("%s %s\n", &h, &n);
  auto ab = new int[][](n, 2);
  auto vi = new int[](h+1);
  vi[] = int.max;
  vi[h] = 0;
  foreach (i; 0..n) {
    ab[i] = readln.chomp.split.to!(int[]);
  }
  sort(ab);

  foreach_reverse(j; 1..h+1) {
    if (vi[j] == int.max) continue;
    foreach (i; 0..n) {
      auto d = max(j - ab[i][0], 0);
      auto pd = j;
      while (d != 0) {
        if (vi[d] > vi[pd] + ab[i][1]) {
          vi[d] = vi[pd] + ab[i][1];
          pd = d;
          d = max(j - ab[i][0], 0);
        } else {
          break;
        }
      }
      if (vi[d] > vi[pd] + ab[i][1]) {
        vi[d] = vi[pd] + ab[i][1];
      }
    }
  }
  
  vi[0].writeln;
}
