#include <bits/stdc++.h>
#define ll long long
using namespace std; const int N = 300005;
int n, k, a[N], cnt[N][2];
ll dp[N][2], inf = 1e18;
// dp[i][1/0] co chon a[i] hay khong
// cnt[i][1/0] dem so doan da toa ra
bool alien(ll P) {
for(int i=1;i<=n;++i) {
dp[i][0] = dp[i-1][0];
cnt[i][0] = cnt[i-1][0];
if (dp[i][0] < dp[i-1][1]) {
dp[i][0] = dp[i-1][1];
cnt[i][0] = cnt[i-1][1];
}
else if (dp[i][0] == dp[i-1][1]) cnt[i][0] = max(cnt[i][0], cnt[i-1][1]);
dp[i][1] = dp[i-1][0] + a[i] - P;
cnt[i][1] = cnt[i-1][0] + 1;
if(dp[i][1] < dp[i-1][1] + a[i]) {
dp[i][1] = dp[i-1][1] + a[i];
cnt[i][1] = cnt[i-1][1];
}
else if (dp[i][1] == dp[i-1][1] + a[i]) cnt[i][1] = max(cnt[i][1], cnt[i-1][1]);
}
if(dp[n][0] > dp[n][1]) return cnt[n][0] >= k;
else if(dp[n][0] < dp[n][1]) return cnt[n][1] >= k;
else return max(cnt[n][0],cnt[n][1]) >= k;
}
int main() {
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin >> n >> k;
for(int i=1;i<=n;++i) cin >> a[i];
ll l = 0, r = inf;
dp[0][1] = -inf;
while(l <= r) {
ll mid = (l+r)/2;
if(alien(mid)) l = mid + 1;
else r = mid - 1;
}
r = max(0LL, r);
alien(r);
cout << max(dp[n][0], dp[n][1]) + r * k;
return 0;
}
