import java.util.*

fun main(args: Array<String>) {
    val (H, N) = readIntList()
    val list = Array(N) { readIntList().toPair() }.sortedBy { it.first }

    val mp = IntArray(H + 1) { Int.MAX_VALUE }
    mp[0] = 0
    for (h in 0 until H) {
        if (mp[h] == Int.MAX_VALUE) continue
        for ((a, b) in list) {
            val tag = if (h+a > H) H else h+a
            mp[tag] = Math.min(mp[tag], mp[h]+b)
        }
    }

    println(mp[H])
}

fun readString() = readLine()!!
fun readStringList() = readLine()!!.split(" ")
fun readInt() = readLine()!!.toInt()
fun readLong() = readLine()!!.toLong()
fun readIntList() = readLine()!!.split(" ").map(String::toInt)
fun readLongList() = readLine()!!.split(" ").map(String::toLong)

fun <E> List<E>.toPair() = this[0] to this[1]