fun main(args: Array<String>) {
    val (H, N) = readLine()!!.split(" ").map(String::toInt)
    val AB = (1..N).map { readLine()!!.split(" ").map(String::toInt) }
    val A = arrayOf(0) + AB.map { a -> a[0] }
    val B = arrayOf(0) + AB.map { a -> a[1] }
    var dp = Array(N + 1) { IntArray(H + 1) }
    for (i in 1..N) dp[i][0] = 0
    for (j in 0..H) dp[0][j] = Int.MAX_VALUE
    for (i in 1..N) {
        for (j in 1..H) {
            val jj = Math.max(0, j - A[i])
            dp[i][j] = Math.min(dp[i - 1][j], dp[i][jj] + B[i])
        }
    }
    println(dp[N][H])
}
