fun main(args: Array<String>) {
  val (H, N) = readInts()
  val AB = (1..N).map { readInts() }

  val dp = Array(H + 1) { Int.MAX_VALUE / 2 }
  dp[H] = 0
  for (i in H downTo 0) {
    for (j in 0 until N) {
      val (A, B) = AB[j]
      // 魔力 B で A の攻撃
      val v = dp[i] // 現在使用している魔力
      val hp = Math.max(i - A, 0) // 攻撃後の残り体力, 0 以下にはならない
      dp[hp] = Math.min(dp[hp], v + B)
    }
  }

  println(dp[0])
}

fun readString() = readLine()!!
fun readStrings() = readString().split(" ")
fun readInt() = readString().toInt()
fun readInts() = readStrings().map { it.toInt() }
fun readLong() = readString().toLong()
fun readLongs() = readStrings().map { it.toLong() }
