import kotlin.math.min

fun intList() = readLine()?.split(" ")?.map(String::toInt) ?: TODO()
fun main() {
    data class Magic(val damage: Int, val cost: Int)
    val (h, n) = intList()
    val magic = 0.until(n).map{
        val (a, b) = intList()
        Magic(a, b)
    }
    val costs = Array(h + 1) { 1e9.toInt() }
    costs[0] = 0
    0.until(h + 1).forEach { i ->
        magic.forEach { m ->
            val d = min(m.damage + i, h)
            costs[d] = min(costs[d], m.cost + costs[i])
        }
    }
    println(costs[h].toString())
}