#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,i,k;
ll v[300005],din[300005],cnt[300005],sum[300005];
ll suma(int st,int dr)
{
return sum[dr]-sum[st-1];
}
ll ok (ll mij)
{
deque <int> st;
st.push_back(0);
for (int i=1; i<=n; i++)
{
din[i]=din[i-1];
cnt[i]=cnt[i-1];
if (din[i]<din[i-1]+mij)
{
din[i]=din[i-1]+mij;
cnt[i]=cnt[i-1]+1;
}
if (st.empty())
{
if (din[i]<v[i]+din[i-1]+mij)
{
din[i]=v[i]+din[i-1]+mij;
cnt[i]=1+cnt[i-1];
}
}
else
{
if (din[i]<din[st.front()]+suma(st.front()+1,i)+mij)
{
din[i]=din[st.front()]+suma(st.front()+1,i)+mij;
cnt[i]=1+cnt[st.front()];
}
}
while (!st.empty()&&din[st.back()]+suma(st.back()+1,i+1)<=v[i+1]+din[i])
{
st.pop_back();
}
st.push_back(i);
}
return cnt[n];
}
ll st,dr,sol;
int main()
{
ios_base :: sync_with_stdio(false);
cin.tie(0);
#ifdef HOME
ifstream cin("date.in");
ofstream cout("date.out");
#endif // HOME
cin>>n>>k;
for (i=1; i<=n; i++)
{
cin>>v[i];
sum[i]=sum[i-1]+v[i];
}
st=-1e16;
dr=1e16;
while (st<=dr)
{
ll mij = (st+dr)/2;
auto salut = ok(mij);
if (salut>=k)
{
sol=mij;
dr=mij-1;
}
else
{
st=mij+1;
}
}
deque <int> st;
st.push_back(0);
for (int i=1; i<=n; i++)
{
din[i]=din[i-1];
cnt[i]=cnt[i-1];
if (din[i]<din[i-1]+sol)
{
din[i]=din[i-1]+sol;
cnt[i]=cnt[i-1]+1;
}
if (st.empty())
{
if (din[i]<v[i]+din[i-1]+sol)
{
din[i]=v[i]+din[i-1]+sol;
cnt[i]=1+cnt[i-1];
}
}
else
{
int poz=st.front();
if (din[i]<din[poz]+suma(poz+1,i)+sol)
{
din[i]=din[poz]+suma(poz+1,i)+sol;
cnt[i]=1+cnt[poz];
}
}
while (!st.empty()&&din[st.back()]+suma(st.back()+1,i+1)<=v[i+1]+din[i])
{
st.pop_back();
}
st.push_back(i);
}
cout<<din[n]-cnt[n]*sol;
return 0;
}
