#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; }