dp 광고 비용 계산

// Baekjoon - 1106  
// https://www.acmicpc.net/problem/1106  
  
use std::cmp::min;  
use std::io::{self, Read, Write};  
  
fn main() {  
    let mut stdin = io::stdin().lock();  
    let mut stdout = io::stdout().lock();  
    let mut input = String::new();  
    stdin.read_to_string(&mut input).unwrap();  
    let mut lines = input.lines();  
  
    let mut costs: Vec<(usize, usize)> = vec![];  
    let first_line: Vec<usize> = lines  
        .next()  
        .unwrap()  
        .split_whitespace()  
        .map(|x| x.parse().unwrap())  
        .collect();  
  
    let target = first_line[0];  
    let n = first_line[1];  
  
    for _ in 0..n {  
        let tmp: Vec<usize> = lines  
            .next()  
            .unwrap()  
            .split_whitespace()  
            .map(|x| x.parse().unwrap())  
            .collect();  
  
        costs.push((tmp[0], tmp[1]));  
    }  
    let max_target = target + 101;  
    let mut dp = vec![usize::MAX; max_target + 1];  
    dp[0] = 0;  
    for i in 0..(max_target) {  
        if dp[i] == usize::MAX {  
            continue;  
        }  
        for &(cost, customers) in &costs {  
            let next = i + customers;  
            if next <= max_target {  
                dp[next] = min(dp[next], dp[i] + cost);  
            }        }    }  
    let output = dp[target..=max_target].iter().min().unwrap();  
    write!(stdout, "{}", output).unwrap();  
}

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val firstLine = readLine()!!.split(" ").map { it.toInt() }
    val target = firstLine[0]
    val cnt = firstLine[1]

    val costs = mutableListOf<Pair<Int, Int>>()

    repeat(cnt) {
        val tmp = readLine()!!.split(" ").map { it.toInt() }
        costs.add(Pair(tmp[0], tmp[1]))
    }
    val maxVal = target * 2
    val dp = MutableList(maxVal) { Int.MAX_VALUE }
    dp[0] = 0

    for (i in 0 until maxVal) {
        if (dp[i] == Int.MAX_VALUE) {
            continue
        }

        for ((cost, customers) in costs) {
            val next = i + customers
            if (next <= maxVal) {
                dp[next] = min(dp[next], dp[i] + cost)
            }
        }
    }

    var minCost = Int.MAX_VALUE
    for (i in target..maxVal) {
        if (dp[i] != Int.MAX_VALUE) {
            minCost = min(minCost, dp[i])
        }
    }
    println(minCost)
    close()
}