#include <bits/stdc++.h>
typedef std::pair <long long, int> pa;
int n, k;
std::vector <int> a;
std::vector <std::vector <pa>> dp;
pa g(long long l) {
for (int i = 0; i < n; i++) for (int j = 0; j < 2; j++) dp[i][j] = { -1, -1 };
auto f = [&] (auto&& self, int i, bool is) -> pa {
if (i >= n) {
return { 0, 0 };
}
if (dp[i][is].second != -1) {
return dp[i][is];
}
dp[i][is] = self(self, i + 1, false);
pa cand = self(self, i + 1, true);
cand.second += !is;
cand.first += a[i];
cand.first -= l * !is;
dp[i][is] = std::max(dp[i][is], cand);
return dp[i][is];
};
return f(f, 0, false);
}
int main() {
std::ios::sync_with_stdio(0); std::cin.tie(0);
std::cin >> n >> k;
dp.resize(n, std::vector <pa> (2));
a.resize(n);
for (int& x : a) {
std::cin >> x;
}
long long l = 0, r = 1LL << 42, ans = 0;
while (l <= r) {
long long mid = (l + r) >> 1;
pa val = g(mid);
if (val.second > k) {
l = mid + 1;
} else {
r = mid - 1;
ans = val.first + mid * k;
}
}
std::cout << ans << "\n";
}
