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 = LongArray(h + 1) { Int.MAX_VALUE.toLong() }
    dp[0] = 0

    for (i in 0 until n) {
        val (damage, mp) = magics[i]
        for (damageSum in 0 until h) {
            val min = Math.min(damageSum + damage, h)
            dp[min] = Math.min(dp[min], dp[damageSum] + mp)
        }
    }

    val answer = dp[h]

    println(answer)
}

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