#include <bits/stdc++.h>
using namespace std;
//#define TESTS
#define x first
#define y second
#define pii pair<int,int>
#define veci vector<int>
#define vecp vector<pii>
#define all(x) x.begin(), x.end()
#define pb(x,y) x.push_back(y)
#define int long long
const int maxn = 3e5+5;
const int maxb = 40;
int n,k, v[maxn];
//costul daca termini la i
int d[maxn], mxd[maxn], arrd[maxn];
bool good(int l)
{
for(int i=0;i<n;i++)
{
d[i]=v[i]-l;
mxd[i]=0;
arrd[i]=1;
}
for(int i=1;i<n;i++)
{
if(d[i]<=d[i-1]+v[i])
{
d[i]=d[i-1]+v[i];
arrd[i]=arrd[i-1];
}
if(d[i]<=d[mxd[i-1]]+v[i]-l)
{
d[i]=d[mxd[i-1]]+v[i]-l;
arrd[i]=arrd[mxd[i-1]]+1;
}
mxd[i]=(d[i]>d[mxd[i-1]]) ? i : mxd[i-1];
}
return arrd[mxd[n-1]] >=k;
}
void solve()
{
cin>>n>>k;
for(int i=0;i<n;i++) cin>>v[i];
int l=0;
for(int b=(1ll<<maxb); b>0; b>>=1)
{
if(good(l+b)) l+=b;
}
good(l);
cout<<d[mxd[n-1]]+l*arrd[mxd[n-1]]<<'\n';
}
int32_t main()
{
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(0);
int t=1;
#ifdef TESTS
cin>>t;
#endif
while(t--)
{
solve();
}
return 0;
}
