#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
ios_base::sync_with_stdio(false); cin.tie(0);
int n, k; cin >> n >> k;
vector<int> a(n + 1);
for(int i = 1; i <= n; i++) cin >> a[i];
for(int i = 1; i <= n; i++) a[i] += a[i - 1];
auto calc = [&](int mid) -> pair<int, int> {
vector<pair<int, int>> dp(n + 1);
for(int i = 1; i <= n; i++){
dp[i] = max(dp[i - 1], {dp[0].first + a[i] - mid, dp[0].second + 1});
dp[0] = max(dp[0], {dp[i].first - a[i], dp[i].second});
}
return dp[n];
};
int l = 0, r = 3e14, ans = -1e18;
while(l <= r){
int mid = (l + r) / 2;
if(calc(mid).second >= k) ans = calc(mid).first + mid * k, l = mid + 1;
else r = mid - 1;
}
cout << ans << '\n';
}
