import kotlin.math.min

fun main() {
  val (h,n) = readLine()!!.split(' ').map { it.toInt() }
  val dp = IntArray(h+1){1000000000}
  dp[0] = 0
  for(i in 0 until n){
    val (value, cost) = readLine()!!.split(' ').map { it.toInt() }
    for(j in 0 until h){
      val k = min(h, j+value)
      dp[k] = min(dp[k], dp[j]+cost)
    }
  }
  println(dp[h])
}