#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;
#define int long long
#define PI pair<int,int>
#define f first
#define s second
#define pb push_back
#define szo(x) ((int)x.size())
const int INF = 1e18;
const int maxn = 3e5+10;
int n, k;
int nums[maxn];
int dp[maxn];
int cnt[maxn];
PI solve(int m){
for (int i = 0; i <= n; ++i) dp[i] = 0, cnt[i] = 0;
int best = 0;
int idbest = 0;
for (int i = 1; i <= n; ++i){
dp[i] = dp[i-1];
cnt[i] = cnt[i-1];
best += nums[i];
if (best-m >= dp[i]){
dp[i] = best-m;
cnt[i] = cnt[idbest] + 1;
}
if ((dp[i] > best) || ((dp[i] == best) && cnt[i] >= cnt[idbest])){
best = dp[i];
idbest = i;
}
}
return {dp[n], cnt[n]};
}
int32_t main(){
ios_base::sync_with_stdio(false); cin.tie(0);
cin >> n >> k;
for (int i = 1; i <= n; ++i) cin >> nums[i];
int x = 1e18;
for (int b = 1e18; b >= 1; b >>= 1){
while (x-b >= 0 && solve(x-b).s <= k) x -= b;
}
cout << solve(x).f + k * x << '\n';
return 0;
}
