import std.stdio, std.conv, std.array, std.string, std.algorithm, std.container, std.range, core.stdc.stdlib, std.math, std.typecons;
T[][] combinations(T)(T[] s, in int m) {   if (!m) return [[]];   if (s.empty) return [];   return s[1 .. $].combinations(m - 1).map!(x => s[0] ~ x).array ~ s[1 .. $].combinations(m); }

alias Magic = Tuple!(long, "damage", long, "magicPoint");

void main() {
  long H, N; readf("%d %d\n", &H, &N);
  auto Magics = N
    .iota
    .map!(i => readln.split.to!(long[]))
    .map!(m => Magic(m[0], m[1]))
    .array();

  long solve() {
    long[long] dp;
    dp[H] = 0;

    long answer = long.max;
    while(true) {
      long[long] nextDp;
      bool updated = false;
      foreach(hp; dp.keys) {
        if (answer <= dp[hp]) continue;
        foreach(magic; Magics) {
          if (answer <= dp[hp]) continue;
          long used = dp[hp] + magic.magicPoint;
          long damaged = hp - magic.damage;
          if (damaged <= 0) {
            if (answer > used) answer = used;
            continue;
          }
          if (damaged in nextDp && nextDp[damaged] < used) continue;
          nextDp[damaged] = used;
          updated = true;
        }
      }
      if (!updated) break;
      dp = nextDp;
    }

    return answer;
  }

  solve().writeln;
}
