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 0..n - 1 { 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 + 1]).min(k)] = dp2[j + 1][(l + c[i + 1]).min(k)].max(dp1[j][l] + a[i + 1]); } } dp1 = dp2.clone(); dp2 = vec![vec![isize::MIN; k + 1]; d + 1]; } let mut ans = isize::MIN; for j in 0..d + 1 { ans = ans.max(dp1[j][k]); } if ans == isize::MIN { println!("No"); } else { println!("{}", ans); } }