#include<bits/stdc++.h> #define f first #define s second using namespace std; long long n; long long k; long long a[300001]; long long cost=0; pair<long long,long long> dp[300001][2]; long long c=0; void read() { cin>>n>>k; for(long long i=1;i<=n;i++) { cin>>a[i]; } } void mrpropa() { for(int i=0;i<=n;i++) { dp[i][1]={0,0}; dp[i][0]={0,0}; } } long long check(long long costh) { cost=costh; mrpropa(); dp[1][0]={0,0}; dp[1][1]={a[1]-cost,1}; for(long long i=2;i<=n;i++) { dp[i][0]=max(dp[i-1][0],dp[i-1][1]); dp[i][1]=max(dp[i-1][1],(pair<long long,long long>){dp[i-1][0].f-cost,dp[i-1][0].s+1}); dp[i][1].f+=a[i]; } dp[n][0].f+=k*cost; dp[n][1].f+=k*cost; pair<int,int>h=max(dp[n][0],dp[n][1]); return h.s; } long long bins() { long long l=0,r=1e18,mid; //cout<<"sere mi se "<<l<<" "<<r<<endl; long long ans=0; while(l<=r) { mid=(l+r)/2; long long h=check(mid); //cout<<mid<<" "<<h<<endl; if(h>k) { l=mid+1; } else r=mid-1; } //cout<<l<<endl; return l; } int main() { read(); //fein(); long long h=check(bins()); long long ans=max(dp[n][0].f,dp[n][1].f); cout<<ans<<endl; return 0; }