fun main(args: Array<String>) {
    abc153e()
}

fun abc153e() {
    val (h, n) = readLine()!!.split(' ').map { it.toInt() }
    val magics = (1..n)
        .map { readLine()!!.split(' ').map { it.toInt() }.let { Magic(it[0], it[1]) } }

    val dp = Array(n + 1) { IntArray(h + 1) { Int.MAX_VALUE / 10 } }
    dp[0][0] = 0

    for (i in 0 until n) {
        val (dmg, mp) = magics[i]
        for (j in 0..h) {
            dp[i + 1][j] = Math.min(dp[i + 1][j], dp[i][j])
            val next = Math.min(j + dmg, h)
            dp[i + 1][next] = Math.min(dp[i + 1][next], dp[i + 1][j] + mp)
        }
    }

    val answer = dp[n][h]

    println(answer)
}

private data class Magic(val damage: Int, val mp: Int)
