#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using i128 = __int128_t;
pair<i128,int> dpc(const vector<ll>& pfs, i128 C){
int n = pfs.size()-1;
vector<i128> dp(n+1, (i128)LLONG_MIN*2);
vector<int> cnt(n+1, 0);
dp[0]=0;
cnt[0]=0;
i128 val=0;
int cnt0=0;
for(int i = 1; i <= n; i++){
dp[i]=dp[i-1];
cnt[i]=cnt[i-1];
i128 dpi = val+(i128)pfs[i]+C;
int ci = cnt0+1;
if(dpi>dp[i]){
dp[i]=dpi;
cnt[i]=ci;
}
i128 cur = dp[i]-(i128)pfs[i];
if(cur>val){
val=cur;
cnt0=cnt[i];
}
}
return { dp[n], cnt[n] };
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, k;
cin >> n >> k;
vector<ll> a(n+1), pfs(n+1, 0);
for(int i=1; i<=n; i++){
cin>>a[i];
pfs[i] = pfs[i-1]+a[i];
}
if (*max_element(a.begin()+1, a.end())<=0) {
cout<<0<<"\n";
return 0;
}
i128 lo=(i128)-1e14, hi=1e14;
i128 c0=hi, dp0=0;
while(lo<=hi){
i128 mid = lo + ((hi-lo)>>1);
auto [dpC, kC] = dpc(pfs, mid);
if(kC>=k){
c0=mid;
dp0=dpC;
hi = mid-1;
}
else lo = mid+1;
}
i128 ans128 = dp0 - c0 * k;
ll ans = (ll)ans128;
cout << ans << "\n";
return 0;
}
