#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef pair<long long, long long> pll;
typedef pair<int,int> pii;
typedef vector<long long> vl;
typedef vector<int> vi;
int n, k;
vi arr;
ll dp[2010][2010][2];
ll f(int at, int segments, int taken){
if(at >= n)
return 0;
if(segments > k)
return 0;
if(dp[at][segments][taken] != -1)
return dp[at][segments][taken];
ll best = 0;
best = max(best, arr[at] + f(at + 1, segments, 1));
if(taken == 0)
best = max(best, f(at + 1, segments, 0));
if(segments + 1 < k && taken == 1)
best = max(best, f(at + 1, segments + 1, 0));
return dp[at][segments][taken] = best;
}
int main(){
cin>>n>>k;
arr.resize(n);
int cnt = 0;
for(int i = 0; i < n; i++){
cin>>arr[i];
if(arr[i] < 0) cnt++;
}
if(cnt == 0){
ll ans = 0;
for(int i = 0; i < n; i++) ans += arr[i];
cout<<ans<<endl;
}
else if(cnt == 1){
ll left = 0, right = 0, flag = 0, pos = -1;
for(int i = 0; i < n; i++){
if(arr[i] < 0){
pos = i;
flag = 1;
}
else if(flag == 0) left += arr[i];
else right += arr[i];
}
cout<<max(max(left, right), left + right + arr[pos]);
}
else if(k == 1){
ll ans = 0, help = 0;
for(int i = 0; i < n; i++){
help += arr[i];
if(ans < help) ans = help;
if(help < 0) help = 0;
}
cout<<ans<<endl;
}
else{
memset(dp, -1, sizeof dp);
cout<<f(0, 0, 0)<<endl;
}
return 0;
}
