import java.io.{BufferedReader, InputStreamReader}

import scala.collection.mutable.ArrayBuffer

object Main {
  def main(args: Array[String]): Unit = {
    val in = new BufferedReader(new InputStreamReader(System.in))
    val Array(h, n) = in.readLine().split("\\s+").map(_.toInt)
    val magicSpecs = (1 to n).map { _ =>
      in.readLine().split("\\s+").map(_.toInt) match {
        case Array(a, b) => (a, b)
      }
    }.foldLeft(new ArrayBuffer[(Int, Int)](n)) {
      case (acc, spec) => acc += spec
    }

    val dp = Array.fill[Int](h + 1)(Integer.MAX_VALUE)
    dp(0) = 0

    for {
      (a, b) <- magicSpecs
      i <- (0 to h)
    } {
      val totalMp = dp(i)
      if (totalMp != Integer.MAX_VALUE) {
        val totalDamage = Math.min(i + a, h)
        dp(totalDamage) = Math.min(dp(totalDamage), totalMp + b)
      }
    }

    System.out.println(dp(h))
  }
}
