fn read() -> T { let mut s = String::new(); std::io::stdin().read_line(&mut s).ok(); s.trim().parse().ok().unwrap() } fn read_vec() -> Vec { read::() .split_whitespace() .map(|e| e.parse().ok().unwrap()) .collect() } fn main() { let v:Vec = read_vec(); let (n, p) = (v[0], v[1]); let mut a = vec![0i32; n]; let mut b = vec![0i32; n]; let mut c = vec![0i32; n]; for i in 0..n { let v:Vec = read_vec(); a[i] = v[0]; b[i] = v[1]; c[i] = v[2]; } let mut dp = vec![vec![std::i32::MAX; p + 1]; n + 1]; dp[0][0] = 0; for ni in 0..n { for pi in 0..p + 1{ if dp[ni][pi] == std::i32::MAX { continue; } if pi + 0 <= p { dp[ni + 1][pi + 0] = std::cmp::min(dp[ni + 1][pi + 0], dp[ni][pi] + a[ni]); } if pi + 1 <= p { dp[ni + 1][pi + 1] = std::cmp::min(dp[ni + 1][pi + 1], dp[ni][pi] + b[ni]); } if pi + 2 <= p { dp[ni + 1][pi + 2] = std::cmp::min(dp[ni + 1][pi + 2], dp[ni][pi] + c[ni]); } if pi + 3 <= p { dp[ni + 1][pi + 3] = std::cmp::min(dp[ni + 1][pi + 3], dp[ni][pi] + 1); } } } // println!("{:?}", dp); println!("{:?}", dp[n][p] as f32 / n as f32); }