#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const long long INF = 1e18;
const int MAXN = 300005;
int n, k;
vector<int> a;
// Global DP arrays to prevent reallocation overhead (Speed optimization)
// storing {score, count}
pair<long long, int> dp0[MAXN]; // Gap state
pair<long long, int> dp1[MAXN]; // Active state
// Returns {max_score, items_picked} for a given penalty lambda
pair<long long, int> check(long long lambda) {
// Base cases
// dp0[0]: In a gap at index 0 (didn't pick a[0])
dp0[0] = {0, 0};
// dp1[0]: Active at index 0 (Must have started a new segment)
// Note: We pay the lambda cost immediately upon starting
dp1[0] = {a[0] - lambda, 1};
for (int i = 1; i < n; i++) {
// --- 1. Calculate DP0 (Gap State) ---
// We are NOT eating a[i]. Came from Gap(i-1) or Active(i-1).
// If scores are equal, we usually prefer fewer segments to be safe,
// but standard max logic works fine here.
if (dp0[i-1].first >= dp1[i-1].first) {
dp0[i] = dp0[i-1];
} else {
dp0[i] = dp1[i-1];
}
// --- 2. Calculate DP1 (Active State) ---
// We ARE eating a[i].
// Option A: Extend current segment (Free, just add a[i])
long long extend_score = dp1[i-1].first + a[i];
int extend_cnt = dp1[i-1].second;
// Option B: 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;
if (start_new_score > extend_score) {
dp1[i] = {start_new_score, start_new_cnt};
} else {
dp1[i] = {extend_score, extend_cnt};
}
}
// Return the better of the two final states
if (dp0[n-1].first > dp1[n-1].first) return dp0[n-1];
return dp1[n-1];
}
int main() {
// Optimization for faster I/O
ios_base::sync_with_stdio(false);
cin.tie(NULL);
if (!(cin >> n >> k)) return 0;
a.resize(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
// Binary Search Range
// Low must be 0 (At most K logic).
// High is roughly max possible sum (3e14), 1e15 is safe.
long long low = 0, high = 1e15;
long long ans_lambda = 0;
while (low <= high) {
long long mid = low + (high - low) / 2;
pair<long long, int> res = check(mid);
// If we pick >= K segments, the penalty is too cheap (or just right).
// We want the largest penalty that still gives us >= K segments
// (closest to touching the curve at K).
if (res.second >= k) {
ans_lambda = mid;
low = mid + 1; // Try to increase penalty
} else {
high = mid - 1;
}
}
// Final Reconstruction
pair<long long, int> final_res = check(ans_lambda);
// If the best lambda (0) still gave us < K segments, it means
// it's optimal to pick fewer than K. The rest are empty segments (sum 0).
// In that case, the formula adds 0 * K, which is correct.
// However, if we forced it with a positive lambda, we add back K * lambda.
long long answer = final_res.first + (long long)k * ans_lambda;
cout << answer << endl;
return 0;
}
