import scala.collection.mutable

object Main {
  def main(args: Array[String]): Unit = {
    val sc = new java.util.Scanner(System.in)
    val monsterHP = sc.nextInt()
    val magicKinds = sc.nextInt()

    val magics = Array
      .fill(magicKinds)(new Magic(sc.nextInt(), sc.nextInt()))
      .sortBy(m => (m.mpPerformance, m.attackPoint))
      .reverse

    val ans = dp(magics, monsterHP)
    println(ans)
  }

  val cache: mutable.Map[Int, Int] = scala.collection.mutable.Map()

  def dp(magics: Array[Magic], currentHP: Int): Int = {
    cache.get(currentHP) match {
      case Some(value) => value
      case None =>
        val nonFatalMagics = magics.filter(_.attackPoint < currentHP)
        val fatalMagic =
          magics
            .filter(_.attackPoint >= currentHP)
            .sortBy(_.magicPoint)
            .headOption
        val mps = nonFatalMagics.map { m =>
          val hpAfterAttack = currentHP - m.attackPoint
          dp(magics, hpAfterAttack) + m.magicPoint
        }
        val minMp = fatalMagic match {
          case Some(value) => (mps :+ value.magicPoint).min
          case None        => mps.min
        }
        cache(currentHP) = minMp
        minMp
    }
  }
}

class Magic(val attackPoint: Int, val magicPoint: Int) {
  val mpPerformance: Double = attackPoint.toDouble / magicPoint.toDouble
}
