let input = readLine()!.split(separator: " ").map { Int($0)! }
let H = input[0]
let N = input[1]
var A: [Int] = .init(repeating: 0, count: N)
var B: [Int] = .init(repeating: 0, count: N)

for i in 0..<N {
  let tmp = readLine()!.split(separator: " ").map { Int($0)! }
  A[i] = tmp[0]
  B[i] = tmp[1]
}

var dp: [Int] = .init(repeating: Int.max, count: H + 1)
dp[0] = 0

for i in 1...H {
  for j in 0..<A.count {
    let offset = i - A[j] >= 0 ? dp[i - A[j]] : 0
    dp[i] = min(dp[i], B[j] + offset)
  }
}
print(dp[H])