use proconio::input; use std::collections::HashMap; fn main() { input! { n: usize, d: usize, k: usize, a: [isize; n], c: [usize; n], } let mut dp = vec![vec![HashMap::new(); d + 1]; n]; dp[0][0].insert(0, 0); dp[0][1].insert(c[0], a[0]); let mut ans = isize::MIN; if c[0] >= k { ans = ans.max(a[0]); } for i in 0..n - 1 { for j in 0..d { for (l, old_val) in dp[i][j].clone() { if let Some(val) = dp[i + 1][j].get_mut(&l) { *val = (*val).max(old_val); } else { dp[i + 1][j].insert(l, old_val); } let new_val = old_val + a[i + 1]; if let Some(val) = dp[i + 1][j + 1].get_mut(&(l + c[i + 1])) { *val = (*val).max(new_val); } else { dp[i + 1][j + 1].insert(l + c[i + 1], new_val); } if l + c[i + 1] >= k { ans = ans.max(new_val); } } } } if ans == isize::MIN { println!("No"); } else { println!("{}", ans); } }