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
    }

    def min(a: Option[Int], b: Option[Int]): Option[Int] = {
      Array(a, b).flatten match {
        case Array(a, b) => Some(Math.min(a, b))
        case Array(a) => Some(a)
        case Array() => None
      }
    }

    val dp = Array.fill[Option[Int]](h + 1)(None)
    dp(0) = Some(0)

    for {
      (a, b) <- magicSpecs
      i <- (0 to h)
      totalMp <- dp(i)
    } {
      val totalDamage = Math.min(i + a, h)
      dp(totalDamage) = min(dp(totalDamage), Some(totalMp + b))
    }
    
    System.out.println(dp(h).get)
  }
}
