/** * https://github.com/matchamgmg/kyopro/tree/main */ #include #include using namespace std; using namespace atcoder; using ll = long long; using ld = long double; using mint = modint998244353; // using mint = modint1000000007; template using pq = priority_queue>; // 大きい順 template using pq_g = priority_queue, greater>; // 小さい順 #define rep(i, s, n) for (int i = (s); i < (int)(n); i++) #define rrep(i, s, n) for (int i = (n - 1); i >= (int)(s); i--) #define all(a) a.begin(), a.end() #define rall(a) a.rbegin(), a.rend() void pyes() { cout << "Yes" << endl; } void pno() { cout << "No" << endl; } void YN(bool x) { cout << (x ? "Yes" : "No") << endl; } template void v_cout(const vector &a) { int n = a.size(); rep(i, 0, n) cout << a[i] << " "; cout << endl; } template void vv_cout(const vector &a) { int n = a.size(); rep(i, 0, n) { rep(j, 0, a[i].size()) cout << a[i][j] << " "; cout << endl; } } bool grid_check(int x, int y, int X, int Y) { return (0 <= x && x < X && 0 <= y && y < Y); } template bool chmax(T &a, T b) { if (a < b) { a = b; return true; } else { return false; } } template bool chmin(T &a, T b) { if (a > b) { a = b; return true; } else { return false; } } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); ll N, K; cin >> N >> K; vector A(N); rep(i, 0, N) { cin >> A[i]; } const ll INF = 1e18; vector> dp(2, vector(K + 1, -INF)); dp[0][0] = 0; rep(i, 0, N) { vector> old_dp(2, vector(K + 1, -INF)); swap(dp, old_dp); rep(k, 0, K + 1) { // 選ばなかった chmax(dp[0][k], old_dp[0][k]); chmax(dp[0][k], old_dp[1][k]); // 選んだ if (k < K && old_dp[0][k] != -INF) { chmax(dp[1][k + 1], old_dp[0][k] + A[i]); } } } if (max(dp[0][K], dp[1][K]) == -INF) { cout << "Impossible" << endl; } else { cout << max(dp[0][K], dp[1][K]) << endl; } }