#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 fein() { dp[1][0]={0,0}; dp[1][1]={a[1],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],{dp[i-1][0].f,dp[i-1][0].s+1}); dp[i][1].f+=a[i]; } c=max(dp[n][0].f,dp[n][1].f); } 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]; } return max(dp[n][0].s,dp[n][1].s); } long long bins() { long long l=0,r=c,mid; //cout<<"sere mi se "<<l<<" "<<r<<endl; 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+k*cost,dp[n][1].f+k*cost); cout<<ans<<endl; return 0; }