#include<bits/stdc++.h> using namespace std; #define endl '\n' #define int long long const int MAXN=3*1e5; int a[MAXN+1]; pair<int,int> cmp(pair<int,int> a,pair<int,int> b){ if(a.first!=b.first){ if(a.first>b.first){ return a; } return b; } if(a.second<b.second){ return a; } return b; } pair<int,int> solve(int pen,int n){ pair<int,int> DP[n+1][2]; for(int i=0;i<=n;i++){ for(int j=0;j<2;j++){ DP[i][j]={-1,-1}; } } DP[0][0]={0,0}; DP[0][1]={-1,-1}; for(int i=0;i<n;i++){ DP[i+1][0]=cmp(DP[i][0],DP[i][1]); DP[i+1][1]=cmp({DP[i][0].first+a[i+1]-pen,DP[i][0].second+1},{DP[i][1].first+a[i+1],DP[i][1].second}); } return cmp(DP[n][0],DP[n][1]); } signed main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); int n,k; cin >> n >> k; for(int i=1;i<=n;i++){ cin >> a[i]; } pair<int,int> x=solve(0,n); if(x.second<=k){ cout << x.first; return 0; } int low=1,high=1e15; low--,high++; while(high-low>1){ int mid=((high-low)>>1)+low; x=solve(mid,n); if(x.second<=k){ high=mid; } else{ low=mid; } } x=solve(high,n); cout << x.first+k*high; }