#include <bits/stdc++.h>
using i64 = long long;
constexpr i64 inf = 1ll << 55;
using D = std::array<std::array<std::vector<i64>, 2>, 2>;
std::vector<i64> mergeConcave(const std::vector<i64> &a, const std::vector<i64> &b) {
const int sl = (int)a.size(), sr = (int)b.size();
std::vector<i64> ret(sl + sr - 1);
int j = 1;
i64 val = a[0] + b[0];
ret[0] = val;
for (int i = 1; i < sl; ++i) {
while (j != sr and b[j] - b[j - 1] > a[i] - a[i - 1]) {
val += b[j] - b[j - 1];
ret[i - 1 + j] = val;
++j;
}
val += a[i] - a[i - 1];
ret[i + j - 1] = val;
}
while (j != sr) {
val += b[j] - b[j - 1];
ret[sl - 1 + j] = val;
++j;
}
return ret;
}
void chmax(std::vector<i64> &a, const std::vector<i64> &b) {
const int n = (int)std::min(a.size(), b.size());
for (int i = 0; i < n; ++i) a[i] = std::max(a[i], b[i]);
}
void chmax(i64 &a, const i64 b) {
if (a < b) a = b;
}
void solve() {
int N, K;
std::cin >> N >> K;
std::vector<i64> A(N);
for (auto &e : A) std::cin >> e;
auto merge = [&](const D &dl, const D &dr) {
const int sl = (int)dl[0][0].size(), sr = (int)dr[0][0].size();
D ret;
for (int x = 0; x < 2; ++x) {
for (int y = 0; y < 2; ++y) {
ret[x][y].assign(sl + sr - 1, -inf);
}
}
for (int xl = 0; xl < 2; ++xl) {
for (int xr = 0; xr < 2; ++xr) {
for (int yl = 0; yl < 2; ++yl) {
for (int yr = 0; yr < 2; ++yr) {
// merge !
// ret[xl][yr] <- dl[xl][xr] * dr[yl][yr]
const auto &a = dl[xl][xr], &b = dr[yl][yr];
auto &res = ret[xl][yr];
if (xr == 1 and yl == 1) {
int j = 1;
i64 val = a[0] + b[0];
// chmax(res[0], val);
for (int i = 1; i < sl; ++i) {
while (j != sr and b[j] - b[j - 1] > a[i] - a[i - 1]) {
val += b[j] - b[j - 1];
chmax(res[i - 1 + j - 1], val);
++j;
}
val += a[i] - a[i - 1];
chmax(res[i + j - 1 - 1], val);
}
while (j != sr) {
val += b[j] - b[j - 1];
chmax(res[sl - 1 + j - 1], val);
++j;
}
// res[0] = -inf;
} else {
int j = 1;
i64 val = a[0] + b[0];
chmax(res[0], val);
for (int i = 1; i < sl; ++i) {
while (j != sr and b[j] - b[j - 1] > a[i] - a[i - 1]) {
val += b[j] - b[j - 1];
chmax(res[i - 1 + j], val);
++j;
}
val += a[i] - a[i - 1];
chmax(res[i + j - 1], val);
}
while (j != sr) {
val += b[j] - b[j - 1];
chmax(res[sl - 1 + j], val);
++j;
}
}
}
}
}
}
for (int x = 0; x < 2; ++x) {
for (int y = 0; y < 2; ++y) {
for (int i = 1; i < sl + sr - 1; ++i) {
ret[x][y][i] = std::max(ret[x][y][i], ret[x][y][i - 1]);
}
}
}
chmax(ret[0][0], ret[0][1]);
chmax(ret[1][0], ret[1][1]);
chmax(ret[0][0], ret[1][0]);
chmax(ret[0][1], ret[1][1]);
return ret;
};
auto solve = [&](auto &&self, const int l, const int r) -> D {
if (r - l == 1) {
D ret;
ret[0][0] = {0, A[l]};
ret[0][1] = {-inf, A[l]};
ret[1][0] = {-inf, A[l]};
ret[1][1] = {-inf, A[l]};
return ret;
}
const int m = (l + r) / 2;
const auto lRes = self(self, l, m), rRes = self(self, m, r);
const auto ret = merge(lRes, rRes);
return ret;
};
const auto res = solve(solve, 0, N);
i64 answer = res[0][0][K];
std::cout << answer << std::endl;
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
solve();
}
