28 lines
841 B
Swift
28 lines
841 B
Swift
if let line1 = readLine(),
|
|
let CN = line1.split(separator: " ").compactMap({Int($0)}) as? [Int],
|
|
let C = CN.first, let N = CN.last
|
|
{
|
|
var info: [(cost: Int, customer: Int)] = []
|
|
for _ in 1...N {
|
|
guard let line2 = readLine(),
|
|
let cost_customer = line2.split(separator: " ").compactMap({Int($0)}) as? [Int],
|
|
let cost = cost_customer.first, let customer = cost_customer.last
|
|
else { break }
|
|
|
|
info.append((cost: cost, customer: customer))
|
|
}
|
|
|
|
var dp: [Int] = Array(repeating: Int.max, count: C + 101)
|
|
dp[0] = 0
|
|
|
|
for (cost, customer) in info {
|
|
for i in customer...(C+100) {
|
|
if dp[i-customer] != Int.max {
|
|
dp[i] = min(dp[i], dp[i-customer] + cost)
|
|
}
|
|
}
|
|
}
|
|
|
|
print(dp[C...].min()!)
|
|
}
|