#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;
const int MAXN = 300005;
ll A[MAXN];
int N, K;
pair<ll, int> solve_with_penalty(ll penalty) {
vector<pair<ll, int>> dp0(N + 1), dp1(N + 1);
for (int i = 1; i <= N; i++) {
if (dp0[i-1].first >= dp1[i-1].first) {
dp0[i] = dp0[i-1];
} else {
dp0[i] = dp1[i-1];
}
pair<ll, int> start_new = {dp0[i-1].first + A[i] - penalty, dp0[i-1].second + 1};
pair<ll, int> continue_old = {dp1[i-1].first + A[i], dp1[i-1].second};
if (start_new.first > continue_old.first) {
dp1[i] = start_new;
} else if (start_new.first < continue_old.first) {
dp1[i] = continue_old;
} else {
dp1[i] = (start_new.second > continue_old.second ? start_new : continue_old);
}
}
return (dp0[N].first >= dp1[N].first ? dp0[N] : dp1[N]);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cin >> N >> K;
for (int i = 1; i <= N; i++) cin >> A[i];
ll low = 0, high = 1e15;
ll ans_penalty = 0;
while (low <= high) {
ll mid = low + (high - low) / 2;
if (solve_with_penalty(mid).second >= K) {
ans_penalty = mid;
low = mid + 1;
} else {
high = mid - 1;
}
}
pair<ll, int> res = solve_with_penalty(ans_penalty);
cout << res.first + (ll)K * ans_penalty << endl;
return 0;
}
