#include <bits/stdc++.h>
using namespace std;
int main(){
cin.tie(0);
ios_base::sync_with_stdio(0);
int n, k;
cin >> n >> k;
long long a[n+1];
for (int i = 1; i <= n; i++) cin >> a[i];
long long s = 0, e = 3 * 1e14;
pair<long long, int> dp[n+1][2];
while (s != e){
long long m = (s + e+1) / 2;
dp[0][0] = {0, 0};
dp[0][1] = {LLONG_MIN, LLONG_MIN};
for (int i = 1; i <= n; i++){
if (dp[i-1][0].first > dp[i-1][1].first){
dp[i][0] = dp[i-1][0];
}
if (dp[i-1][0].first < dp[i-1][1].first){
dp[i][0] = dp[i-1][1];
}
if (dp[i-1][0].first == dp[i-1][1].first){
dp[i][0] = {dp[i-1][0].first, max(dp[i-1][0].second, dp[i-1][1].second)};
}
if (dp[i-1][0].first - m > dp[i-1][1].first){
dp[i][1] = {dp[i-1][0].first + a[i] - m, dp[i-1][0].second + 1};
}
if (dp[i-1][0].first - m < dp[i-1][1].first){
dp[i][1] = {dp[i-1][1].first + a[i], dp[i-1][1].second};
}
if (dp[i-1][0].first - m == dp[i-1][1].first){
dp[i][1] = {dp[i-1][1].first + a[i], max(dp[i-1][0].second + 1, dp[i-1][1].second)};
}
}
long long amo;
if (dp[n][0].first > dp[n][1].first){
amo = dp[n][0].second;
}
if (dp[n][0].first < dp[n][1].first){
amo = dp[n][1].second;
}
if (dp[n][0].first == dp[n][1].first){
amo = max(dp[n][1].second, dp[n][0].second);
}
if (amo < k){
e = m - 1;
}
else{
s = m;
}
}
long long m = s;
dp[0][0] = {0, 0};
dp[0][1] = {LLONG_MIN, LLONG_MIN};
for (int i = 1; i <= n; i++){
if (dp[i-1][0].first > dp[i-1][1].first){
dp[i][0] = dp[i-1][0];
}
if (dp[i-1][0].first < dp[i-1][1].first){
dp[i][0] = dp[i-1][1];
}
if (dp[i-1][0].first == dp[i-1][1].first){
dp[i][0] = {dp[i-1][0].first, max(dp[i-1][0].second, dp[i-1][1].second)};
}
if (dp[i-1][0].first - m > dp[i-1][1].first){
dp[i][1] = {dp[i-1][0].first + a[i] - m, dp[i-1][0].second + 1};
}
if (dp[i-1][0].first - m < dp[i-1][1].first){
dp[i][1] = {dp[i-1][1].first + a[i], dp[i-1][1].second};
}
if (dp[i-1][0].first - m == dp[i-1][1].first){
dp[i][1] = {dp[i-1][1].first + a[i], max(dp[i-1][0].second + 1, dp[i-1][1].second)};
}
}
cout << s * k + max(dp[n][0].first, dp[n][1].first);
}
