
function Main(input) {
  input=input.split("\n");
  if(input[input.length-1]===''){
    input.pop();
  }
  const H=input[0].split(' ')[0]-0;
  const N=input[0].split(' ')[1]-0;
  var memo=[0];
  var A=input.map(e=>{
    return e.split(' ')[0]-0;
  });
  A.shift();
  var B=input.map(e=>{
    return e.split(' ')[1]-0;
  });
  B.shift();
  var min;
  for(var i=1;i<=H;i++){
    min=Infinity;
    for(var j=0;j<N;j++){
      if(i<=A[j]){
        min=Math.min(min,B[j]);
      }else{
        min=Math.min(min,B[j]+memo[i-A[j]]);
      }
    }
    memo.push(min);
  }
  console.log(memo[H]);
}


//*この行以降は編集しないでください（標準入出力から一度に読み込み、Mainを呼び出します）
Main(require("fs").readFileSync("/dev/stdin", "utf8"));
  



  
