#include <array>
#include <iostream>
#include <tuple>
#include <vector>
int main() {
int n, k;
std::cin >> n >> k;
std::vector<int> v(n);
for (int& i : v) std::cin >> i;
long long lo = 0, hi = 1e15;
long long score = 0, amount = 0;
while (lo < hi) {
long long m = (lo + hi + 1) / 2;
std::vector<std::array<std::pair<long long, int>, 2>> dp(n + 1);
dp[0][1].first = -1e18;
for (int i = 1; i <= n; ++i) {
dp[i][1] = dp[i - 1][1];
if (dp[i - 1][0].first - m > dp[i][1].first || (dp[i - 1][0].first + m == dp[i][1].first && dp[i - 1][0].second + 1 > dp[i][1].second)) {
dp[i][1] = dp[i - 1][0];
dp[i][1].first -= m;
++dp[i][1].second;
}
dp[i][1].first += v[i - 1];
dp[i][0] = dp[i - 1][0];
if (dp[i - 1][1].first > dp[i][0].first || (dp[i - 1][1].first == dp[i][0].first && dp[i - 1][1].second > dp[i][0].second)) {
dp[i][0] = dp[i - 1][1];
}
}
std::pair<long long, int> max = dp[n][0];
if (dp[n][1].first > max.first || (dp[n][1].first == max.first && dp[n][1].second > max.second)) max = dp[n][1];
if (max.second >= k) {
lo = m;
std::tie(score, amount) = max;
} else {
hi = m - 1;
}
}
std::cout << score + (amount * lo) << '\n';
return 0;
}
