fun main(args: Array<String>) {
    val (H, N) = readLine()!!.split(" ").map(String::toInt)
    val attacks = Array(N) { readLine()!!.split(" ").map(String::toInt).let { it[0] to it[1] } }

    val maxMp = attacks.maxBy { it.second }!!.second

    val dp = arrayOfNulls<Long>(H + 1 + maxMp)
    dp[0] = 0
    for (i in 1..H + maxMp) {
        for ((attack, mp) in attacks) {
            if (i - attack >= 0 && dp[i - attack] != null) {
                dp[i] = Math.min(dp[i] ?: Long.MAX_VALUE, mp + dp[i - attack]!!)
            }
        }
    }

//    dp.forEach(::println)
    dp.sliceArray(H..H + maxMp).filterNotNull().min().let(::println)

}

