#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int n, k;
const long long INF = 1e18;
// Returns {max_score, items_picked} for a given penalty lambda
pair<long long, int> check(vector<int> &a , long long lambda) {
vector<pair<long long, int>> dp0(n); // Gap state
vector<pair<long long, int>> dp1(n); // Active state
// --- FIX 1: Correct Base Cases ---
// Gap at 0: We didn't eat a[0]. Score 0, Segments 0.
dp0[0] = {0, 0};
// Active at 0: We started a new segment at a[0].
dp1[0] = {a[0] - lambda, 1};
for (int i = 1; i < n; i++) {
// --- DP0 (GAP) ---
// We are NOT eating a[i]. We came from Gap(i-1) or Active(i-1).
// If scores equal, prefer FEWER segments (min) or MORE (max)?
// Standard practice: just take max tuple (compares first, then second).
if (dp0[i-1] >= dp1[i-1]) {
dp0[i] = dp0[i-1];
} else {
dp0[i] = dp1[i-1];
}
// --- DP1 (ACTIVE) ---
// We ARE eating a[i].
// Option 1: Extend existing segment (Free)
// FIX 2: You MUST add a[i] to the score!
long long extend_score = dp1[i-1].first + a[i];
int extend_cnt = dp1[i-1].second;
// Option 2: Start new segment (Pay Lambda)
long long start_new_score = dp0[i-1].first + a[i] - lambda;
int start_new_cnt = dp0[i-1].second + 1;
// Compare
if (start_new_score > extend_score) {
dp1[i] = {start_new_score, start_new_cnt};
} else {
dp1[i] = {extend_score, extend_cnt};
}
}
// Return the best of the two final states
if (dp0[n-1].first > dp1[n-1].first) return dp0[n-1];
return dp1[n-1];
}
int main() {
cin >> n >> k;
vector<int> a(n);
for (auto &x : a) cin >> x;
// FIX 3: Allow negative lambda (bonus) for negative inputs
long long low = -1e15, high = 1e15, ans_lambda = -1e18;
while (low <= high) {
long long mid = low + (high - low) / 2;
pair<long long, int> res = check(a, mid);
// If we have >= K segments, the penalty is too cheap (or just right).
// We need to INCREASE penalty to reduce count, or store answer.
if (res.second >= k) {
ans_lambda = mid;
low = mid + 1;
} else {
high = mid - 1;
}
}
pair<long long, int> final_res = check(a, ans_lambda);
// Formula: Unconstrained_Score + (Target_K * Lambda)
long long final_ans = final_res.first + (long long)k * ans_lambda;
cout << final_ans << endl;
return 0;
}
