#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector<ll>;
using vvl = vector<vll>;
using vb = vector<bool>;
using pll = pair<ll,ll>;
using vpl = vector<pll>;
using vvp = vector<vpl>;
#define f first
#define s second
#define pb push_back
#define all(v) v.begin(),v.end()
vll a, rs;
ll n;
pll calc(ll lam){
vpl dp(n+1);
pll mx={0,0};
for(ll i = 1; i<=n; ++i){
dp[i] = max<pll>(dp[i-1], {mx.f+rs[i]-lam, mx.s-1});
mx = max<pll>(mx, {dp[i].f-rs[i], dp[i].s});
}
return dp[n];
}
int main(){
ios_base::sync_with_stdio(0);cin.tie(NULL);
ll k;
cin >> n >> k;
a = vll(n);
rs = vll(n+1);
for(ll i = 0; i < n; ++i){
cin >> a[i];
rs[i+1]=rs[i]+a[i];
}
ll ans;
ll s=0, e=1e18;
while(s<e){
pll ret = calc((s+e)/2);
if(-ret.s>k)s=(s+e)/2+1;
else{ans=ret.f+k*((s+e)/2);e=(s+e)/2;}
}
cout << ans;
}
