// #define MINHDEPTRAI "/Volumes/icebear/source_code/VS_code"
#ifdef MINHDEPTRAI
#include "/Library/Developer/CommandLineTools/usr/include/c++/v1/bits/stdc++.h"
#include <chrono>
#define __gcd(a, b) gcd(a, b)
using namespace std ::chrono;
#else
#include <bits/stdc++.h>
#endif
using namespace std;
#define foru(i, a, b) for (int i = a; i <= b; ++i)
#define ford(i, a, b) for (int i = a; i >= b; --i)
#define forr(i, l, r) for (int i = (l); i < (r); ++i)
#define IOS cin.tie(0),cout.tie(0)->sync_with_stdio(0);
#define mp(a, b) make_pair(a, b)
#define int long long
typedef pair<int, int> pii;
typedef pair<pair<int, int>, int> piii;
#define endl '\n'
using ld = long double;
const string name_minh = "maxcross";
const int maxN = 2e3 + 5;
const int maxK = 2e5 + 5;
const int mod = 1e9 + 7;
const long long inf = 1e18;
int dp[maxN][maxN][2], cnt_negative, arr[maxN];
int n, k;
void k_1(){
int current = 0, best = -inf;
foru(i, 1, n){
current = max(arr[i], current + arr[i]);
best = max(best, current);
}
cout << best;
}
int prefix_sum[maxK];
void solve(){
cin >> n >> k;
foru(i, 1, n) {
cin >> arr[i];
prefix_sum[i] = prefix_sum[i - 1] + arr[i];
if(arr[i] < 0) cnt_negative++;
}
if(k == 1){
k_1();
return;
}
else if(cnt_negative == 0){
cout << prefix_sum[n] << endl;
}
else if(cnt_negative == 1){
foru(i, 1, n){
if(arr[i] < 0){
int beggin = prefix_sum[i - 1];
int endd = prefix_sum[n] - prefix_sum[i];
if(k >= 2) cout << beggin + endd << endl;
else cout << max({beggin, endd, beggin + endd + arr[i]});
break;
}
}
}
else {
foru(i, 1, n){
foru(j, 1, k){
dp[i][j][0] = max(dp[i - 1][j][1], dp[i - 1][j][0]);
dp[i][j][1] = max({dp[i - 1][j - 1][1], dp[i - 1][j][1], dp[i - 1][j - 1][0]}) + arr[i];
}
}
cout << max(dp[n][k][0], dp[n][k][1]) << endl;
}
}
signed main() {
IOS
// #ifndef MINHDEPTRAI
// freopen((name_minh + ".in").c_str(), "r", stdin);
// freopen((name_minh + ".out").c_str(), "w", stdout);
// #endif
int t = 1;
while(t--){
solve();
}
}
