// {{{1
extern "C" int __lsan_is_turned_off() { return 1; }
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <string>
#include <iostream>
#include <deque>
using namespace std;
#define ll long long
#define inf 0x3f3f3f3f
#define infl 0x3f3f3f3f3f3f3f3f
#define ninf 0xbebebebe
#define ninfl 0xbebebebebebebebe
#ifdef DEBUG
#define dprintf(args...) fprintf(stderr,args)
#include <assert.h>
#endif
#ifndef DEBUG
#define dprintf(args...) 69
#define assert(args...) 42
#endif
// 1}}}
int main()
{
int n,nk;scanf("%d %d",&n,&nk);
dprintf("n=%d nk=%d\n",n,nk);
vector<int> a(n);for(auto&x:a)scanf("%d",&x);
/*
vector<vector<ll>> dp(nk+1, vector<ll>(n,0));
for(int i=0;i<n;i++)dp[0][i] = 0;
for(int k=1;k<=nk;k++) {
ll x=0;
for(int i=0;i<n;i++) {
if(i)x = max(x,dp[k-1][i-1]);
dp[k][i] = (x += a[i]);
if(i) dp[k][i] = max(dp[k][i],dp[k][i-1]);
else dp[k][i] = max(0ll,dp[k][i]);
}
}
*/
auto dp = [&](ll B) {
vector<ll> dp(n), cnt(n);
/* let dp_B [i] = best cost for [0...i]
// given cnt[i] subarrays,
// where each subarray costs B
//
// dp\[-1] = 0
// dp\[i] = max( dp\[i-1], -\ + max [j<=i] (dp\[j-1] + sum a_j..i ) )
*/
ll x=0,cx=0; // represents max[j<=i] dp[j-1]+sum a_j..i
for(int i=0;i<n;i++) {
dp[i] = i?dp[i-1]:0; cnt[i]=i?cnt[i-1]:0;
x+=a[i];
//printf("x=%lld cx=%lld B=%lld x-B=%lld\n",x,cx,B,x-B);
if(x-B > dp[i]) dp[i]=x-B, cnt[i]=cx+1;
if(dp[i]>x) x=dp[i],cx=cnt[i];
//dp[i] = max(i?dp[i-1]:0, (x+=a[i]) - B);
//x=max(x, dp[i]);
//printf("i=%d dp=%lld cnt=%lld\n",i,dp[i],cnt[i]);
}
//printf("n-1=%d dp=%lld cnt=%lld\n",n-1,dp[n-1],cnt[n-1]);
return pair<vector<ll>,vector<ll>>{dp, cnt};
};
ll lB = 0, rB = 1e18;
while(lB<rB) {
ll mB = lB+(rB-lB)/2;
dprintf("B %lld %lld %lld\n",lB,mB,rB);
auto [Bdp, cnt] = dp(mB);
dprintf("cnt %lld\n",cnt[n-1]);
if(cnt[n-1] > nk) lB=mB+1;
else rB=mB;
}
auto [Bdp, cnt] = dp(lB);
//for(auto x:Bdp)printf("%lld ",x);printf("\n");
//for(auto x:cnt)printf("%lld ",x);printf("\n");
dprintf("%lld %lld %lld\n",Bdp[n-1],lB,nk);
printf("%lld\n",Bdp[n-1] + lB * nk);
//printf("%lld\n",dp[nk][n-1]);
}
