export {};
const input = require("fs").readFileSync(0).toString().trim().split("\n");

const [C, N]: number[] = input[0].split(" ").map(Number);
let dp: number[] = Array(C+101).fill(Infinity);
dp[0] = 0;

for(let n = 1; n<=N; n++) {
    const [cost, man]: number[] = input[n].split(" ").map(Number);

    for(let i=man; i<C+101; i++) {
        if(dp[i-man] !== Infinity) {
            dp[i] = Math.min(dp[i], dp[i-man] + cost);
        }
    }
}

let ans: number = dp[C];
for(let i=1; i<=100; i++) ans = Math.min(ans, dp[C+i]);
console.log(ans);