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