#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using i128 = __int128_t;
struct Node {
i128 val;
int cnt;
Node(i128 v = (i128)-9e36, 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;
return (a.cnt < b.cnt) ? a : b; // prefer fewer segments on tie
}
pair<i128,int> solve_with_lambda(const vector<ll> &A, i128 lambda){
int n = (int)A.size();
Node dp((i128)0, 0); // best for prefix
Node best_end((i128)-9e36,0); // best that ends at current i
for (int i = 0; i < n; ++i){
Node extend = Node(best_end.val + (i128)A[i], best_end.cnt);
Node start_new = Node(dp.val + (i128)A[i] - lambda, dp.cnt + 1);
best_end = better(extend, start_new);
dp = better(dp, best_end);
}
return {dp.val, dp.cnt};
}
// helper to print i128
string to_string_i128(i128 x){
if (x == 0) return "0";
bool neg = false;
if (x < 0){ neg = true; x = -x; }
string s;
while (x > 0){
int digit = (int)(x % 10);
s.push_back('0' + digit);
x /= 10;
}
if (neg) s.push_back('-');
reverse(s.begin(), s.end());
return s;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N;
long long K;
if (!(cin >> N >> K)) return 0;
vector<ll> A(N);
for (int i = 0; i < N; ++i) cin >> A[i];
// set safe search bounds (i128)
// choose bounds based on absolute sum to reduce useless extremes
i128 sumAbs = 0;
for (ll x : A) sumAbs += (i128) llabs(x);
i128 lo = -sumAbs - 1; // a bit more margin
i128 hi = sumAbs + 1;
// binary search largest lambda such that cnt >= K
while (lo < hi) {
i128 mid = lo + (hi - lo + 1) / 2;
auto [val, cnt] = solve_with_lambda(A, mid);
if (cnt >= (int)K) lo = mid;
else hi = mid - 1;
}
i128 lambda = lo;
auto [val, cnt] = solve_with_lambda(A, lambda);
i128 answer = val + lambda * (i128)K; // safe in i128
cout << to_string_i128(answer) << '\n';
return 0;
}
