//O(N log N)
// https://oj.uz/problem/view/NOI19_feast
// Lagrangian Relaxation
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int N, K;
vector<int> values;
ll totalScore = 0;
bool solve(ll cost){
vector<ll> run(N + 1);
vector<ll> no(N + 1);
vector<ll> uses(N + 1);
for(int i = 1; i <= N; i++){
int val = values[i - 1];
uses[i] = uses[i - 1];
run[i] = run[i - 1] + val;
ll potential = no[i - 1] + val - cost;
if(potential > run[i]){
run[i] = potential;
uses[i] += 1;
}
if(run[i] < 0){
run[i] = 0;
uses[i]--;
}
no[i] = max({
no[i - 1],
run[i]
});
}
ll c = uses[N] + 1;
totalScore = max(run[N], no[N]) + cost * c;
return c > K;
}
int main(){
ios::sync_with_stdio(0); cin.tie(0);
cin >> N >> K;
values.resize(N);
for(int i = 0; i < N; i++){
cin >> values[i];
}
ll low = 0; ll high = 1e18;
while(low < high){
ll mid = (low + high) / 2;
if(solve(mid)){ //if c >= K
low = mid + 1;
}else{
high = mid;
}
}
solve(low);
cout << totalScore;
// int A_; cin >> A_;
return 0;
}
