import java.lang.Math

fun main(args: Array<String>) {
    val (H, N) = readInputLine().split(" ").map { it.toInt() }
    val magic = Array(N) { val (A, B) = readInputLine().split(" ").map { it.toInt() }; Pair(A, B)}

    // ダメージを与えるために必要な最低のMP
    val dp = IntArray(H + 1) { Int.MAX_VALUE }
    dp[0] = 0

    for (i in 0 until H) {
        if (dp[i] == Int.MAX_VALUE) {
            continue
        }
        for (m in magic) {
            val next = Math.min(H, i + m.first)
            dp[next] = Math.min(dp[next], dp[i] + m.second)
        }
    }

    println(dp[H])
}

fun readInputLine(): String {
    return readLine()!!
}
