fun main(args: Array<String>) {
    val (H, N) = listOfInt()
    val dp = Array<Int>(H + 1) { 1001001001 }
    dp[0] = 0
    repeat(N) {
        val (A, B) = listOfInt()
        repeat (H) {
            val nh = Math.min(it + A, H)
            dp[nh] = Math.min(dp[nh], dp[it] + B)
        }
    }
    println(dp[H])
}
fun next() = readLine()!!
fun nextLong() = next().toLong()
fun listOfString() = next().split(" ")
fun listOfInt() = listOfString().map(String::toInt)