#include <bits/stdc++.h>
#define f first
#define s second
#define ll long long
using namespace std;
const int maxn=1e7+5;
const int MOD=1e9+7;
int n,k;
vector<int> a;
vector<ll> sum,Max;
vector<vector<ll>> dp;
void sub1(){
if(k==n){
ll tong = 0;
for(int i = 1; i <= n; i++){
tong = tong + a[i];
}
cout << tong << endl;
return;
}
long long tong = 0;
for(int i = 1; i <= n; i++){
if(a[i] > 0){
tong = tong + a[i];
}
}
cout << tong << endl;
return;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>n>>k;
a.assign(n+5,0);
sum.assign(n+5,0);
int cnt=0,pos=0;
for(int i=1;i<=n;i++){
cin>>a[i];
sum[i]=sum[i-1]+a[i];
if(a[i]<0){
cnt++;
pos=i;
}
}
ll ans=-1e18;
if(cnt<=1&&k!=1){
sub1();
}
else{
dp.assign(n+5,vector<ll>(k+5,-1e18));
Max.assign(n+5,0);
for(int i=0;i<=n;i++) dp[i][0]=0;
for(int i=1;i<=n;i++){
Max[i]=max(Max[i-1],-sum[i]);
}
for(int x=1;x<=k;x++){
for(int i=1;i<=n;i++){
dp[i][x]=dp[i-1][x];
dp[i][x]=max(dp[i][x],Max[i-1]+sum[i]);
}
Max[0]=-1e18;
for(int i=1;i<=n;i++){
Max[i]=max(Max[i-1],dp[i][x]-sum[i]);
}
}
for(int i=1;i<=n;i++) ans=max(ans,dp[i][k]);
cout<<ans;
}
}
