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)((sc.nextInt(), sc.nextInt()))

    val dp = Array.fill(monsterHP + 1)(Int.MaxValue)
    dp(0) = 0

    for {
      (attackPoint, magicPoint) <- magics
      i <- (0 to monsterHP)
    } {
      if (dp(i) != Int.MaxValue) {
        val targetHP = Math.min(monsterHP, i + attackPoint)
        dp(targetHP) = Math.min(dp(targetHP), dp(i) + magicPoint)
      }
    }

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

}
