#include<bits/stdc++.h> //#include<bits/extc++.h> #define fi first #define se second #define int long long using namespace std; //using namespace __gnu_pbds; using db=double; using ll=int64_t; using sll=__int128; using lb=long double; mt19937 rng(random_device{}()); int32_t main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n,k; cin>>n>>k; vector<int>a(n+1); for(int i=1; i<=n; i++){ cin>>a[i]; } auto check=[&](int mid)->pair<int,int>{ vector<vector<pair<int,int>>>dp(n+1,vector<pair<int,int>>(2,{-1e18,0ll})); dp[1][0]={0ll,0ll}; dp[1][1]={a[1]-mid,1ll}; for(int i=2; i<=n; i++){ dp[i][0]=max(dp[i-1][0],dp[i-1][1]); dp[i][1]=max(make_pair(dp[i-1][0].fi+a[i]-mid,dp[i-1][0].se+1),make_pair(dp[i-1][1].fi+a[i],dp[i-1][1].se)); } return max(dp[n][0],dp[n][1]); }; int left=0; int right=1e18; while(left<right){ int mid=(left+right+1)>>1; if(check(mid).se>=k)left=mid; else right=mid-1; } cout<<check(left).fi+left*k; } /* Overhead the albatross hangs motionless upon the air And deep beneath the rolling waves in labyrinths of coral caves The echo of a distant time comes willowing across the sand And everything is green and submarine And no one showed us to the land And no one knows the wheres or whys But something stirs and something tries And starts to climb towards the light */