use proconio::input; fn main() { input! { n: usize, d: usize, k: usize, a: [isize; n], c: [usize; n], } let mut dp1 = vec![vec![isize::MIN; k + 1]; d + 1]; let mut dp2 = vec![vec![isize::MIN; k + 1]; d + 1]; dp1[0][0] = 0; dp1[1][c[0].min(k)] = a[0]; for i in 1..n { for j in 0..d { for l in 0..k + 1 { if dp1[j][l] == isize::MIN { continue; } dp2[j][l] = dp2[j][l].max(dp1[j][l]); dp2[j + 1][(l + c[i]).min(k)] = dp2[j + 1][(l + c[i]).min(k)].max(dp1[j][l] + a[i]); } } dp1 = dp2.clone(); dp2 = vec![vec![isize::MIN; k + 1]; d + 1]; } if dp1[d][k] == isize::MIN { println!("No"); } else { println!("{}", dp1[d][k]); } }