#include <algorithm>
#include <array>
#include <ios>
#include <iostream>
#include <utility>
#include <vector>
using State = std::pair<long long, int>;
auto solve() {
auto k = 0;
auto n = 0;
std::cin >> n >> k;
auto a = std::vector<int>(n);
for (auto& x : a) {
std::cin >> x;
}
auto lo = -1ll;
auto mx_pts = 0ll;
for (auto x : a) {
mx_pts += std::max(x, 0);
}
const auto compute = [&](long long penalty) {
auto dp = std::array<State, 2>();
dp[1].first = -(mx_pts + 1);
for (auto x : a) {
const auto maximize = [](State& lhs, const State& rhs) {
auto& [pts_l, cnt_l] = lhs;
const auto& [pts_r, cnt_r] = rhs;
if (pts_r > pts_l || (pts_r == pts_l && cnt_r < cnt_l)) {
lhs = rhs;
}
};
auto new_dp = std::array<State, 2>();
new_dp[0].first = -(mx_pts + 1);
new_dp[1].first = -(mx_pts + 1);
maximize(new_dp[0], dp[0]);
maximize(new_dp[0], State({dp[0].first + x - penalty, dp[0].second + 1}));
maximize(new_dp[1], State({dp[0].first + x, dp[0].second}));
maximize(new_dp[0], State({dp[1].first + x - penalty, dp[1].second + 1}));
maximize(new_dp[1], State({dp[1].first + x, dp[1].second}));
dp = std::move(new_dp);
}
return dp;
};
auto hi = mx_pts + 1;
while (hi - lo > 1) {
const auto mid = (lo + hi) >> 1;
(compute(mid)[0].second < k ? hi : lo) = mid;
}
const auto [pts, cnt] = std::move(compute(lo)[0]);
std::cout << pts + lo * cnt << '\n';
}
auto main() -> int {
std::cin.tie(nullptr);
std::ios_base::sync_with_stdio(false);
solve();
return 0;
}
