import kotlin.math.max
import kotlin.math.min

fun main() {
    val (h, n) = readLine()!!.split(" ").map { it.toInt() }

    val magics = MutableList(n) {
        val (a, b) = readLine()!!.split(" ").map { it.toInt() }
        a to b
    }
    magics.sortByDescending { it.first.toFloat() / it.second }

    val dp = Array(h + 1) { Long.MAX_VALUE / 2 }
    dp[h] = 0
    for (i in 0 until n) {
        for (j in (0..h).reversed()) {
            val nextHp = max(j - magics[i].first, 0)
            dp[nextHp] = min(dp[nextHp], dp[j] + magics[i].second)
        }
    }

    println(dp[0])
}