#include <climits>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int n, k;
// Returns {max_score, items_picked} for a given penalty lambda
pair<long long, int> check(vector<int> &a , long long lambda) {
// dp[i] stores {score, count} for the prefix i
vector<pair<long long, int>> dp0(n);
vector<pair<long long, int>> dp1(n);
// Base cases
dp0[0] = {0,0}; // Pick first item
dp1[0]={a[0]-lambda ,1};
for (int i = 1; i < n; i++) {
//dp0
if( dp0[i-1].first>dp1[i-1].first){
dp0[i] = dp0[i-1] ;
}else dp0[i] = dp1[i-1] ;
//dp1
if ( dp1[i-1].first+a[i]< dp0[i-1].first+a[i]-lambda){
dp1[i]= {dp0[i-1].first+a[i]-lambda, dp0[i-1].second+1} ;
}
else {
dp1[i].first=dp1[i-1].first +a[i];
dp1[i].second=dp1[i-1].second;
}
}
if (dp0[n-1].first > dp1[n-1].first )return dp0[n-1];
return dp1[n - 1];
}
int main() {
// Example input
long long low = INT_MIN, high = 1e15, ans_lambda = -1;
// Binary Search for Lambda
cin >> n >> k ;
vector<int> a(n);
for ( auto &x: a)cin >> x ;
while (low <= high) {
long long mid = low + (high - low) / 2;
pair<long long, int> res = check(a,mid);
if (res.second >= k) {
ans_lambda = mid;
low = mid + 1; // Try to increase penalty to reduce count
} else {
high = mid - 1;
}
}
// Final Answer Reconstruction
pair<long long, int> final_res = check(a, ans_lambda);
long long final_ans = final_res.first + (long long)k * ans_lambda;
cout << final_ans << endl;
return 0;
}
