#include<bits/stdc++.h>
using namespace std;
void speed()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
}
long long int n,k,a[300005],dp1[2005][2005][3],dp[300005][3],num[300005][3];
void dumb()
{
for(int i=1;i<=n;i++)
{
for(int j=1;j<=k;j++)
{
dp1[i][j][0]=max(dp1[i-1][j][0],dp1[i-1][j][1]);
dp1[i][j][1]=max(dp1[i-1][j-1][0],dp1[i-1][j][1])+a[i];
}
}
}
int make_dp(long long int cost)
{
dp[0][1]=-1e18;
for(int i=1;i<=n;i++)
{
if(dp[i-1][0]>dp[i-1][1])
{
dp[i][0]=dp[i-1][0];
num[i][0]=num[i-1][0];
}
else
{
dp[i][0]=dp[i-1][1];
num[i][0]=num[i-1][1];
}
if(dp[i-1][1]>=dp[i-1][0]-cost)
{
dp[i][1]=dp[i-1][1]+a[i];
num[i][1]=num[i-1][1];
}
else
{
dp[i][1]=dp[i-1][0]-cost+a[i];
num[i][1]=num[i-1][0]+1;
}
//cout<<dp[i][0]<<" "<<dp[i][1]<<endl;
}
//cout<<endl;
if(dp[n][0]==dp[n][1])return min(num[n][0],num[n][1]);
if(dp[n][0]<dp[n][1])return num[n][1];
return num[n][0];
}
void read()
{
cin>>n>>k;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
long long int l=1,r=1e18,mid,use,fin;
while(l<=r)
{
mid=(l+r)/2;
use=make_dp(mid);
if(use>=k)l=mid+1;
else r=mid-1;
}
l--;
use=make_dp(l);
//cout<<l<<" "<<use<<" "<<max(dp[n][0],dp[n][1])<<endl;
fin=max(dp[n][0],dp[n][1])+use*l-(use-k)*l;
cout<<fin<<endl;
}
int main()
{
speed();
read();
return 0;
}
