#include <bits/stdc++.h> using namespace std; using ll = long long; #define vi vector<long long> #define all(x) x.begin(), x.end() #define endl "\n" void solution(); int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); solution(); return 0; } const int N = 2010; const long long inf = 1e18; ll dp[N][N][2]; ll a[N]; void solution() { ll n, k; cin >> n >> k; for (int i = 1; i <= n; i++) cin >> a[i]; for (int i = 1; i <= k; i++) dp[0][i][0] = dp[0][i][1] = -inf; for (int i = 1; i <= n; i++) { for (int j = 1; j <= k; j++) { dp[i][j][0] = max({ dp[i-1][j][0] + a[i], dp[i-1][j-1][0] + a[i], dp[i-1][j-1][1] + a[i] }); dp[i][j][1] = max({ dp[i-1][j][0], dp[i-1][j-1][0], dp[i-1][j-1][1] }); } } cout << max(dp[n][k][1], dp[n][k][0]) << endl; }