import Foundation

extension String {
    
    func toStrList() -> [String] {
        return self.map{String($0)}
    }
    
    func toIntList() -> [Int] {
        return self.map{Int(String($0))!}
    }
    
    func toSepDoubleList() -> [Double]{
        return self.split(separator: " ").map{Double($0)!}
    }

    func toSepIntList() -> [Int] {
        return self.split(separator: " ").map{Int($0)!}
    }

    func toSepStrList() -> [String] {
        return self.split(separator: " ").map{String($0)}
    }
    
    func zFill(n:Int) -> String {
        return String(format: "%0\(n)d", Int(self)!)
    }
    
    func count(c:Character) -> Int{
        var result = 0

        for e in self{
            if e == c{
                result += 1
            }
        }
        return result
    }

    func counter() -> Dictionary<Character, Int>{
        var result:[Character:Int] = [:]
        
        for c in self{
            guard let _ = result.index(forKey: c) else {
                result[c] = 1
                continue
            }
            result[c]! += 1
        }
        return result
    }
}

extension Int {
    func toBin() -> String {
        return String(self, radix: 2)
    }
    
    func toNBin(_ radix:Int) -> String{
        return String(self, radix: radix)
    }
    
    func toD() -> Double {
        return Double(self)
    }
}

extension Double {
    func toI() -> Int {
        return Int(self)
    }
}

extension Array where Element: Equatable{
    func count(n:Self.Element) -> Int{
        var result = 0
        for e in self{
            if e == n{
                result += 1
            }
        }
        return result
    }
}

extension Array {
    func dump(){
        for x in 0..<self.count-1{
            print(self[x], terminator: " ")
        }
        print(self.last!)
    }
}

func pow(_ base:Int,_ exp:Int) -> Int{
    let d = pow(base.toD(), exp.toD())
    return Int(d)
}

func distance(p1:CGPoint, p2:CGPoint) -> Double {
    let diffp = CGPoint(x:p1.x - p2.x, y:p1.y - p2.y)
    return Double(sqrt(diffp.x*diffp.x + diffp.y * diffp.y))
}

func distance(p1:[Double], p2:[Double]) -> Double{
    let diff = [p1[0] - p2[0], p1[1] - p2[1]]
    return sqrt(diff[0] * diff[0] + diff[1] * diff[1])
    
}

func lotate(theta:Double, point:[Double]) -> [Double] {
    let matrix = [
        [cos(theta), -sin(theta)],
        [sin(theta), cos(theta)]
    ]
    let x = point[0]
    let y = point[1]
    
    let rx = matrix[0][0]*x + matrix[0][1]*y
    let ry = matrix[1][0]*x + matrix[1][1]*y
    
    return [rx, ry]
}


func abc153e() -> Int {
    let HN = readLine()!.toSepIntList()
    let H = HN[0]
    let N = HN[1]
    var AB = [[Int]](repeating: [], count: N)
    var dp = [Int](repeating: pow(10, 10), count: H+1)
    for i in 0..<N{
        AB[i].append(contentsOf: readLine()!.toSepIntList())
    }
    
    dp[H] = 0
    for i in stride(from: H, to: -1, by: -1){
        for ab in AB {
            if (i-ab[0]) <= 0 {
                dp[0] = min(dp[0], dp[i] + ab[1])
            } else {
                dp[i-ab[0]] = min(dp[i-ab[0]], dp[i] + ab[1])
            }
        }
    }
    return dp[0]
}

print(abc153e())

Measured memory_bytes: 13716