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 ans = Int.max
var memo: [Int] = .init(repeating: -1, count: H + 1)

func dfs(_ A: [Int], _ B: [Int], _ H: Int, _ current: Int) {
  if H <= 0 {
    ans = min(ans, current)
    return
  }
  if ans <= current {
    return
  }
  if memo[H] != -1 && memo[H] <= current {
    return 
  }
  memo[H] = current
  for i in 0..<A.count {
    dfs(A, B, H - A[i], current + B[i])
  }
}

dfs(A, B, H, 0)

print(ans)