// NOI19_Feast
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int nx = 3e5 + 5;
const ll inf = 1e18;
int n, k;
ll a[nx], qs[nx];
pair<ll,int> solve(ll m) {
vector<pair<ll,int>> dp(n + 1, make_pair(-inf, 0));
pair<ll,int> mx = {0, 0};
dp[0] = {0, 0};
for (int i = 1; i <= n; i++) {
mx = max(mx, {dp[i - 1].first - qs[i - 1], dp[i - 1].second});
dp[i] = max(dp[i - 1], {mx.first + qs[i] - m, mx.second + 1});
}
return dp[n];
}
int main() {
ios_base::sync_with_stdio(0), cin.tie(0);
cin >> n >> k;
for (int i = 1; i <= n; i++) {
cin >> a[i];
qs[i] = a[i] + qs[i - 1];
}
ll l = 0, r = 3e14;
while (l < r) {
ll mid = (l + r + 1) >> 1;
if (solve(mid).second >= k) l = mid;
else r = mid - 1;
}
cout << solve(l).first + l * k;
}
