#include <bits/stdc++.h> using namespace std; using ll = long long; void solve(){ ll n, k; cin >> n >> k; vector<ll> v(n); for(ll i = 0; i < n; i++) { cin >> v[i]; } //ll dp[n][k + 1][2]; ll INF = -1e17; vector<vector<vector<ll>>> dp (n, vector<vector<ll>>(k+1, {0, 0})); dp[0][1][1] = v[0]; dp[0][1][0] = v[0]; for (ll i = 0; i <= k; i++) { dp[0][i][1] = v[0]; } for (ll i = 1; i < n; i++) { dp[i][1][1] = max(dp[i - 1][1][1], dp[i - 1][0][0]) + v[i]; for (ll j = 1; j <= k; j++) { vector<ll> temp; temp = {dp[i - 1][j][1], dp[i - 1][j][1] + v[i], dp[i - 1][j - 1][0] + v[i], dp[i - 1][j - 1][1] + v[i], dp[i - 1][j][0]}; dp[i][j][0] = *max_element(temp.begin(), temp.end()); temp = {dp[i - 1][j][1] + v[i], dp[i - 1][j - 1][0] + v[i], dp[i - 1][j - 1][1] + v[i]}; dp[i][j][1] = *max_element(temp.begin(), temp.end()); } } /*for (auto i : dp) { for (auto j : i) { cout << j[0] << " "; } cout << endl; } cout << "idk" << endl; for(auto i : dp) { for (auto j : i) { cout << j[1] << " "; } cout << endl; }*/ ll mMax = 0; for (ll i = 0; i <= k; i++) { mMax = max(mMax, dp[n - 1][i][0]); mMax = max(mMax, dp[n - 1][i][1]); } cout << mMax << endl; } bool single = true; signed main(){ ios_base::sync_with_stdio(false); cout.tie(0); cin.tie(0); ll t = 1; if(!single) cin >> t; while(t--){ solve(); } }