function Main(input){
    input = input.split("\n");
    var mem = input[0].split(" ").map(Number);
    var dp = new Array(20020);
    dp[0] = 0;
    input.shift();
    for(var i=0;i<input.length;i++){
        input[i] = input[i].split(" ").map(Number);
    }
    for(var i=1;i<dp.length;i++){
        var min = Number.MAX_SAFE_INTEGER;
        for(var j=0;j<input.length;j++){
         //   console.log(i,input[j][0])
            if(i-input[j][0]<0) continue;
            else min = Math.min(min,dp[i-input[j][0]]+input[j][1]);
        }
        dp[i] = min
       // console.log(dp)
    }
    var max = 0;
    for(var i=0;i<input.length;i++){
        if(max<input[i][0]) max = input[i][0]
    }
    var ans = Number.MAX_SAFE_INTEGER;
    for(var i=mem[0]-0;i<mem[0]-0+1+max;i++){
        //console.log(dp[i])
        if(ans>dp[i]) ans = dp[i];
    }
    console.log(ans)
}Main(require("fs").readFileSync("/dev/stdin", "utf8").trim());
