// Source: https://usaco.guide/general/io
#include <iostream> // cin, cout
#include <vector> // vector
#include <string> // string
#include <set>
#include <queue>
#include <fstream>
#include <unordered_map>
#include <map>
#define vec vector
#define NEK 1000000000000
#define For(i,n) for(ll i = 0; i < n; i++)
#define ll long long
#define pii pair<int,int>
#define int ll
#define mod 998244353
using namespace std;
pii aliens_trick(int L, vec<int>&a){
//kazdy usek pridavame s penalizacou L: H - L*X
//chceme returnut nasu vyslednu maximalnu hodnotu, a aj pocet usekov ktore na nu vyuzijeme
//ak bude platit ze usekov je menej ako k, chceme useky penalizovat menej cize zvacsit L, v opacnom pripade L zmensit, najdeme idealnu hranicu ktora je vacsia ako k
//teraz bude platit ze nase riesenie s hodnotou H a usekmi X bude mat hodnotu H - L*X, rovnaku ako toto riesenie, sedi kvoli konkavnosti
//cize potom co najdeme nasu hodnotu ktora je H - L*X, uz iba pripocitame L*X (aj ked povodna hodnota ma tvar ineho H1-L*X1) plati totiz H1-L*X1 = H - L*X /+L*X -> = H
int n = a.size();
vec<vec<int>> dp(n+1, vec<int>(2, 0));
vec<vec<int>> k(n+1, vec<int>(2, 0));
for(int i = n-1; i >= 0; i--){
//riesime dp[i][0]
if(dp[i+1][0] == dp[i+1][1] + a[i] - L){
dp[i][0] = dp[i+1][0];
k[i][0] = max(k[i+1][0], k[i+1][1] + 1);
}
else{
if(dp[i+1][0] > dp[i+1][1] + a[i] - L){
dp[i][0] = dp[i+1][0];
k[i][0] = k[i+1][0];
}
else{
if(dp[i+1][0] < dp[i+1][1] + a[i] - L){
dp[i][0] = dp[i+1][1] + a[i] - L;
k[i][0] = k[i+1][1] + 1;
}
}
}
//riesime dp[i][1]
if(dp[i+1][0] == dp[i+1][1] + a[i]){
dp[i][1] = dp[i+1][0];
k[i][1] = max(k[i+1][0], k[i+1][1]);
continue;
}
if(dp[i+1][0] > dp[i+1][1] + a[i]){
dp[i][1] = dp[i+1][0];
k[i][1] = k[i+1][0];
continue;
}
if(dp[i+1][0] < dp[i+1][1] + a[i]){
dp[i][1] = dp[i+1][1] + a[i];
k[i][1] = k[i+1][1];
continue;
}
}
return {dp[0][0], k[0][0]};
}
void solve() {
int n, k;
cin >> n >> k;
vec<int> a(n);
For(i, n) cin >> a[i];
int l = 0;
int r = NEK;
while(l < r){
int mid = (l+r+1)/2;
pii vys = aliens_trick(mid, a);
if(vys.second < k){
r = mid - 1;
}
else{
l = mid;
}
}
int vys = aliens_trick(l, a).first;
cout << vys + l*k << endl;
return;
}
signed main() {
int t; t = 1;
while(t--) solve();
return 0;
}
