#include <bits/stdc++.h>
using namespace std;
long long n,k,a[300001];
void read()
{
cin>>n>>k;
for(long long i=1;i<=n;i++)
cin>>a[i];
}
long long dp[300001][2];
long long cnt[300001][2];
pair<long long,long long> group(long long x)
{
//cout<<"! "<<x<<endl;
dp[0][1]=-1e18;
for(long long i=1;i<=n;i++)
{
dp[i][0]=dp[i-1][0];
cnt[i][0]=cnt[i-1][0];
if(dp[i][0]<dp[i-1][1])
{
dp[i][0]=dp[i-1][1];
cnt[i][0]=cnt[i-1][1];
}
if(dp[i-1][0]==dp[i-1][1])
cnt[i][0]=max(cnt[i-1][0],cnt[i-1][1]);
dp[i][1]=dp[i-1][1]+a[i];
cnt[i][1]=cnt[i-1][1];
if(dp[i][1]<dp[i-1][0]+a[i]-x)
{
dp[i][1]=dp[i-1][0]+a[i]-x;
cnt[i][1]=cnt[i-1][0]+1;
}
if(dp[i-1][1]==dp[i-1][0]-x)
cnt[i][1]=max(cnt[i-1][1],cnt[i-1][0]+1);
//cout<<i<<" "<<dp[i][0]<<" "<<dp[i][1]<<" "<<cnt[i][0]<<" "<<cnt[i][1]<<endl;
}
if(dp[n][0]>dp[n][1])return {dp[n][0],cnt[n][0]};
if(dp[n][0]<dp[n][1])return {dp[n][1],cnt[n][1]};
return {dp[n][0],max(cnt[n][0],cnt[n][1])};
}
void solve()
{
long long ans=0;
long long l=0,r=1e9;
while(l<=r)
{
long long m=(l+r)/2;
pair<long long,long long> g=group(m);
if(g.second>=k)
{
//cout<<"in "<<g.first<<" "<<g.second<<endl;
ans=max(ans,g.first+m*g.second);
l=m+1;
}
else r=m-1;
}
cout<<ans<<endl;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
read();
solve();
return 0;
}
