import java.util.*

fun main(args:Array<String>){
    val (h,n) = readLine()!!.split(" ").map{it.toInt()}
    val a = IntArray(n)
    val b = IntArray(n)
    for(i in 0 until n){
        val (x,y) = readLine()!!.split(" ").map{it.toInt()}
        a[i] = x
        b[i] = y
    }
    val dp = IntArray(h + 1){1000000000}
    dp[0] = 0
    for(i in 0 until n){
        for(j in 0 .. h){
            if(j + a[i] <= h) dp[j + a[i]] = Math.min(dp[j + a[i]], dp[j] + b[i])
            else dp[h] = Math.min(dp[h], dp[j] + b[i])
        }
    }
    println(dp[h])
}
