#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define endl '\n'
#define ll long long
#define int long long
const long long inf=1e18;
const int MOD=998244353;
const int N=3e5+5;
int n,k,a[N];
pair<int,int> dp[N][2];
int func(int lambda){
dp[0][0]={0,0};//empty
dp[0][1]={-lambda,1};//using it
for(int i=1;i<=n;i++){
dp[i][0]=max(dp[i-1][0],dp[i-1][1]);
int x=dp[i-1][0].first-lambda+a[i],y=dp[i-1][1].first+a[i];
if(x>y || (x==y && dp[i-1][0]<dp[i-1][1])){
dp[i][1].first=x;
dp[i][1].second=dp[i-1][0].second+1;
}
else{
dp[i][1].first=y;
dp[i][1].second=dp[i-1][1].second;
}
}
int x=dp[n][0].first,y=dp[n][1].first;
if(x==y && dp[n][1]<dp[n][0])swap(dp[n][0],dp[n][1]);
return (x>y?dp[n][0].second:dp[n][1].second);
}
signed main() {
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin>>n>>k;
for(int i=1;i<=n;i++)cin>>a[i];
int l=0,r=1e18;
while(l<r){
int mid=(l+r+1)/2;
int x=func(mid);
if(x>=k)l=mid;
else r=mid-1;
}
func(l);
cout<<max(dp[n][0].first+l*dp[n][0].second,dp[n][1].first+l*dp[n][1].second);
}
