#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 3e5+10;
pair<ll, int> dp[N];
ll a[N];
ll qs[N];
int n, k;
// dp[i][j] = max with j subarray to index i
// dp[i][j] = max(dp[i][j-1], dp[k][j-1] + sum(k+1, i)); k < i
// dp[i][j] = max(dp[i][j-1], dp[k][j-1] + qs[i] - qs[k]); k < i
// dp[i][j] = max(dp[i][j-1], mx + qs[i]); mx = max(dp[k][l]-qs[k]), k < i, l < j
// dp[i] = max(dp[i-1], mx + qs[i] - lambda)
pair<ll, int> chk(ll lambda){
dp[0] = {0, 0};
pair<ll, int> mx = {0, 0};
for(int i = 1; i <= n; ++i){
dp[i] = dp[i-1];
dp[i] = max(dp[i], {mx.first + qs[i] - lambda, mx.second+1});
mx = max(mx, {dp[i].first-qs[i], dp[i].second});
}
return dp[n];
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> k;
for(int i = 1; i <= n; ++i) cin >> a[i], qs[i] = qs[i-1]+a[i];
ll l = 0, r = 3e14;
while(l < r){
ll mid = (l+r+1)>>1;
if(chk(mid).second >= k) l = mid;
else r = mid-1;
}
cout << chk(l).first + l*k << '\n';
}
