/****ThanhCodeDao*****/
/*******Azazel*******/
#include<bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define pb push_back
#define checkbit(mask,i) ((mask>>i)&1)
#define bit(i) (1<<i)
#define MLog 21
typedef long long ll;
const ll maxN = 3e5+3, modd = 1e9+7;
struct Point{
ll x,y;
};
ll cross(Point p,Point q,Point r){ // vi tri r voi duong pq >0 la ben trai, =0 la thang hang
ll val = (q.x-p.x)*(r.y-q.y) - (q.y-p.y)*(r.x-q.x);
if(val < 0) return -1;
if(val > 0) return 1;
return 0;
}
ll dot(Point vecA,Point vecB){ // tra ve >0 la nhon, <0 la tu, =0 la vuong, 2 vecto phai chung goc
ll val = vecA.x*vecB.x + vecA.y*vecB.y;
if(val < 0) return -1;
if(val > 0) return 1;
return 0;
}
double triarea(Point p,Point q,Point r){ // cross(pq * pr) / 2
double cross = (q.x-p.x)*(r.y-q.y) - (q.y-p.y)*(r.x-q.x);
return fabs(cross)/2.0;
}
/* de cho
cho n so nguyen, chon k day lien tiep sao cho tong lon nhat
*/
/* nhan xet nho
ban dau khong quan tam can qtam chon k hay k+999 day
su dung pair dp[i][0/1] = {sum,cnt} de chon dp lon nhat
voi alien trick hay trick he so phat
ta chat nhi phan 1 he so phat C, moi khi chuyen tu 0 sang 1 thi he so phat se duoc tinh 1 lan vao sum
vi he so phat cang lon thi dp se cang chon it phan tu
vi bai toan lay max nen he so phat se tru vao
nen ta co the truy nguoc sum_real = sum - C*cnt
neu dp[n].cnt <=k => giam he so C
nguoc => tang he so C
*/
/* nhan xet tu thuat trau
*/
int n,k;
ll a[maxN];
pair<ll,int> mxpa(pair<ll,int> p1,pair<ll,int> p2){
if(p1.F == p2.F){
if(p1.S < p2.S) return p1;
return p2;
}
if(p1.F > p2.F) {
return p1;
}else{
return p2;
}
}
pair<ll,int> calc(ll c){
pair<ll,int> f[n+3][2];
f[1][0] = {0,0};
f[1][1] = {a[1]-c,1};
for(int i = 2;i<=n;i++){
f[i][1] = mxpa({f[i-1][0].F + a[i] - c,f[i-1][0].S + 1}, {f[i-1][1].F + a[i],f[i-1][1].S});
f[i][0] = mxpa(f[i-1][0],f[i-1][1]);
}
return mxpa(f[n][0],f[n][1]);
}
void solve() {
cin >> n >> k;
for(int i = 1;i<=n;i++) cin >> a[i];
ll ans = 0;
ll l = 0, r = 1e10;
while(l<=r){
ll cmid = (l+r)/2;
pair<ll,int> dp = calc(cmid);
if(dp.S <= k){
ll sum = dp.F + cmid*dp.S;
ans = max(ans,sum);
r = cmid-1;
}else{
l = cmid+1;
}
}
cout << ans;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
//freopen("inp.txt","r",stdin);
//freopen("out.txt","w",stdout);
solve();
return 0;
}
