#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i, a, b) for (int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
const int INF = 1e17;
const int N = 3e5 + 5;
int n, k;
int a[N];
pii dp[N][2];
pii f(int penatly) {
dp[0][0] = {0, 0};
dp[0][1] = {-INF, -INF};
for (int i = 1; i <= n; ++i) {
dp[i][0] = max(dp[i - 1][0], dp[i - 1][1]);
dp[i][1] = max(make_pair(dp[i - 1][0].first + a[i] - penatly, dp[i - 1][0].second + 1),
make_pair(dp[i - 1][1].first + a[i], dp[i - 1][1].second));
// cout << dp[i][0].first << '-' << dp[i][1].first << ' ';
}
// cout << '\n';
return max(dp[n][0], dp[n][1]);
}
signed main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n >> k;
for (int i = 1; i <= n; ++i) {
cin >> a[i];
}
int penatly = 0, lo = 0, hi = INF;
while (lo <= hi) {
int mid = lo + (hi - lo >> 1);
pii tmp = f(mid);
// cout << mid << ' ' << tmp.first << ' ' << tmp.second << '\n';
if (tmp.second < k) {
hi = mid - 1;
} else {
penatly = mid;
lo = mid + 1;
}
}
// cout << penatly << '\n';
cout << f(penatly).first + f(penatly).second * penatly;
}
