fun main(args:Array<String>) {

    val (h,n) = readLine()!!.split(" ").map { it.toInt() }
    val item = Array(n){0 to 0}

    for(i in 0 until n) {
        val (damage, point) = readLine()!!.split(" ").map { it.toInt() }
        item[i] = damage to point
    }
    val inf = 100000000
    // 10000000
    val dp =Array(h+1){inf}
    dp[0] = 0
    for(i in 0 until n) {
        val (damage, point) = item[i]
        for(j in 1..h) {
            val diff = j - damage
            val prev = if(diff < 0) 0 else diff 
            if(dp[j] > dp[prev]+point) {
                dp[j] = dp[prev]+point
            }
        }
    }
    println(dp[h])
}