#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll NEG = (ll)-9e18;
struct Node {
ll val; // value = sum - lambda * segments
int cnt; // number of segments used
Node(ll v = NEG, int c = 0) : val(v), cnt(c) {}
};
inline Node better(const Node &a, const Node &b){
if (a.val != b.val) return (a.val > b.val) ? a : b;
// tie-break: prefer fewer segments
return (a.cnt < b.cnt) ? a : b;
}
pair<ll,int> solve_with_lambda(const vector<ll> &A, ll lambda){
int n = (int)A.size();
Node dp(0,0); // best for prefix processed so far
Node best_end(NEG,0); // best value for a solution that ends at current i
for (int i = 0; i < n; ++i){
// option 1: extend previous ending segment
Node extend = Node(best_end.val + A[i], best_end.cnt);
// option 2: start new segment at i (pay -lambda)
Node start_new = Node(dp.val + A[i] - lambda, dp.cnt + 1);
best_end = better(extend, start_new);
dp = better(dp, best_end);
}
return {dp.val, dp.cnt};
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N, K;
if (!(cin >> N >> K)) return 0;
vector<ll> A(N);
for (int i = 0; i < N; ++i) cin >> A[i];
// Binary search lambda: find largest lambda such that cnt >= K
ll lo = - (ll)1e15, hi = (ll)1e15;
while (lo < hi) {
ll mid = lo + ((hi - lo + 1) >> 1);
auto [val, cnt] = solve_with_lambda(A, mid);
if (cnt >= K) lo = mid;
else hi = mid - 1;
}
ll lambda = lo;
auto [val, cnt] = solve_with_lambda(A, lambda);
// answer for at most K segments:
ll answer = val + lambda * (ll)K;
cout << answer << '\n';
return 0;
}
