function main(input) {
  var H = input[0].split(" ")[0]-0;
  var N = input[0].split(" ")[1]-0;
  var list = [];
  for(var i=1;i<=N;i++){
    list.push(input[i].split(" ").map(v=>v-0));
  }
  var dp = [0];
  var ans = Number.MAX_VALUE;
  for(var i=1;i<=H;i++){
    var min_mana = Number.MAX_VALUE;
    for(var j=0;j<N;j++){
      var a = list[j][0]; // power 
      var b = list[j][1]; // nama
      if(dp[i-a]){
        min_mana = Math.min(min_mana, dp[i-a] + b);
      }else{
        if(i<=a){
          min_mana = Math.min(min_mana, b);
        }
      }
    }
    dp[i] = min_mana;
  }
  console.log(dp[H]);
}

main(require('fs').readFileSync('/dev/stdin', 'utf8').split("\n"))
