#include <stdio.h>
#define N 300000
#define H_ 19 /* H_ = ceil(log2(N + 1)) */
#define N_ (1 << H_)
#define INF 0x3f3f3f3f3f3f3f3fLL
long long min(long long a, long long b) { return a < b ? a : b; }
long long max(long long a, long long b) { return a > b ? a : b; }
unsigned int X = 12345;
int rand_() {
return (X *= 3) >> 1;
}
long long ppmn[N_ * 2], ppmx[N_ * 2], ssmn[N_ * 2], ssmx[N_ * 2]; int n_;
void pul(int i) {
int l = i << 1, r = l | 1;
ppmn[i] = min(ppmn[l], ppmn[r]);
ppmx[i] = max(ppmx[l], ppmx[r]);
ssmn[i] = min(ssmn[l], ssmn[r]);
if (ppmx[l] != -INF && ppmn[r] != INF)
ssmn[i] = min(ssmn[i], ppmn[r] - ppmx[l]);
ssmx[i] = max(ssmx[l], ssmx[r]);
if (ppmn[l] != INF && ppmx[r] != -INF)
ssmx[i] = max(ssmx[i], ppmx[r] - ppmn[l]);
}
void build(long long *aa, int n) {
int i;
n_ = 1;
while (n_ < n)
n_ <<= 1;
for (i = 0; i < n_; i++) {
if (i < n)
ppmn[n_ + i] = aa[i], ppmx[n_ + i] = aa[i];
else
ppmn[n_ + i] = INF, ppmx[n_ + i] = -INF;
ssmn[n_ + i] = ssmx[n_ + i] = 0;
}
for (i = n_ - 1; i > 0; i--)
pul(i);
}
long long query_mn(int l, int r, int *l_, int *r_) {
static int qu[(H_ + 1) * 2], qu_[H_ + 1];
int cnt, cnt_, hl, hr, hl_, hr_, i;
long long s_;
cnt = cnt_ = 0;
for (l += n_, r += n_; l <= r; l >>= 1, r >>= 1) {
if ((l & 1) == 1)
qu[cnt++] = l++;
if ((r & 1) == 0)
qu_[cnt_++] = r--;
}
while (cnt_--)
qu[cnt++] = qu_[cnt_];
s_ = INF, hl_ = hr_ = -1;
for (hr = 0, hl = -1, l = -1; hr < cnt; hr++) {
r = qu[hr];
if (s_ > ssmn[r])
s_ = ssmn[r], hl_ = hr_ = hr;
if (l != -1 && s_ > ppmn[r] - ppmx[l])
s_ = ppmn[r] - ppmx[l], hl_ = hl, hr_ = hr;
if (ppmx[r] != -INF && (hl == -1 || ppmx[l] < ppmx[r]))
hl = hr, l = r;
}
if (hl_ == hr_) {
i = qu[hl_];
while (i < n_)
if (ssmn[i << 1 | 0] == ssmn[i])
i = i << 1 | 0;
else if (ssmn[i << 1 | 1] == ssmn[i])
i = i << 1 | 1;
else {
l = i << 1 | 0, r = i << 1 | 1;
break;
}
if (i >= n_)
l = r = i;
} else
l = qu[hl_], r = qu[hr_];
while (l < n_)
l = ppmx[l << 1 | 0] == ppmx[l] ? l << 1 | 0 : l << 1 | 1;
while (r < n_)
r = ppmn[r << 1 | 0] == ppmn[r] ? r << 1 | 0 : r << 1 | 1;
*l_ = l - n_, *r_ = r - n_;
return s_;
}
long long query_mx(int l, int r, int *l_, int *r_) {
static int qu[(H_ + 1) * 2], qu_[H_ + 1];
int cnt, cnt_, hl, hr, hl_, hr_, i;
long long s_;
cnt = cnt_ = 0;
for (l += n_, r += n_; l <= r; l >>= 1, r >>= 1) {
if ((l & 1) == 1)
qu[cnt++] = l++;
if ((r & 1) == 0)
qu_[cnt_++] = r--;
}
while (cnt_--)
qu[cnt++] = qu_[cnt_];
s_ = -INF, hl_ = hr_ = -1;
for (hr = 0, hl = -1, l = -1; hr < cnt; hr++) {
r = qu[hr];
if (s_ < ssmx[r])
s_ = ssmx[r], hl_ = hr_ = hr;
if (l != -1 && s_ < ppmx[r] - ppmn[l])
s_ = ppmx[r] - ppmn[l], hl_ = hl, hr_ = hr;
if (ppmn[r] != INF && (hl == -1 || ppmn[l] > ppmn[r]))
hl = hr, l = r;
}
if (hl_ == hr_) {
i = qu[hl_];
while (i < n_)
if (ssmx[i << 1 | 0] == ssmx[i])
i = i << 1 | 0;
else if (ssmx[i << 1 | 1] == ssmx[i])
i = i << 1 | 1;
else {
l = i << 1 | 0, r = i << 1 | 1;
break;
}
if (i >= n_)
l = r = i;
} else
l = qu[hl_], r = qu[hr_];
while (l < n_)
l = ppmn[l << 1 | 0] == ppmn[l] ? l << 1 | 0 : l << 1 | 1;
while (r < n_)
r = ppmx[r << 1 | 0] == ppmx[r] ? r << 1 | 0 : r << 1 | 1;
*l_ = l - n_, *r_ = r - n_;
return s_;
}
long long ss[N + 1]; int m;
void solve(int l, int r, int flip) {
long long s;
int l_, r_;
s = !flip ? query_mx(l, r, &l_, &r_) : query_mn(l, r, &l_, &r_);
if (s != 0) {
ss[m++] = !flip ? s : -s;
solve(l, l_, flip), solve(l_, r_, flip ^ 1), solve(r_, r, flip);
}
}
void sort(long long *ss, int l, int r) {
while (l < r) {
int i = l, j = l, k = r;
long long s = ss[l + rand_() % (r - l)], tmp;
while (j < k)
if (ss[j] == s)
j++;
else if (ss[j] < s) {
tmp = ss[i], ss[i] = ss[j], ss[j] = tmp;
i++, j++;
} else {
k--;
tmp = ss[j], ss[j] = ss[k], ss[k] = tmp;
}
sort(ss, l, i);
l = k;
}
}
int main() {
static long long aa[N + 1];
int n, k, h, i;
long long ans;
scanf("%d%d", &n, &k);
for (i = 1; i <= n; i++)
scanf("%lld", &aa[i]), aa[i] += aa[i - 1];
build(aa, n + 1);
solve(0, n, 0);
sort(ss, 0, m);
ans = 0;
for (h = m - 1; h >= 0 && h >= m - k; h--)
ans += ss[h];
printf("%lld\n", ans);
return 0;
}
