use proconio::input; use std::cmp::max; fn main(){ input!{ n: usize, k: usize, a: [i64; n], } if n < 2*k{ println!("Impossible"); return; } let mut dp = vec![vec![vec![i64::MIN/128; 2]; k+1]; n+1]; dp[0][0][0] = 0; for i in 0..n{ for j in 0..=k{ for l in 0..2{ if l == 0 && j < k{ dp[i+1][j+1][1] = dp[i+1][j+1][l].max(dp[i][j][l]+a[i]); } dp[i+1][j][0] = dp[i+1][j][0].max(dp[i][j][l]); } } } println!("{}", max(dp[n][k][0], dp[n][k][1])); }