https://www.acmicpc.net/problem/1106
fun main() = with(System.`in`.bufferedReader()) {
var (c,n) = readLine().split(" ").map{it.toInt()}
var dp = IntArray(c+101){1000000}
dp[0] =0
repeat(n){
var (cost,get) = readLine().split(" ").map{it.toInt()}
for(i in get until c+101){
dp[i] = Math.min(dp[i],cost+dp[i-get])
}
}
var ans = Int.MAX_VALUE
for(i in c..c+100){
ans = Math.min(ans,dp[i])
}
println(ans)
}