#include <bits/stdc++.h>
using namespace std;
int sir[300001];
int main()
{
ios :: sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
int lungime , limita;
cin >> lungime >> limita;
for (int indice = 1 ; indice <= lungime ; indice++)
{ cin >> sir[indice]; }
int64_t stanga = -1e15 , dreapta = 0 , rezultat = 0;
while (stanga <= dreapta)
{
pair <int64_t , int> maxim[2] = {{-1e15 , 0} , {0 , 0}};
const int64_t termen = (stanga + dreapta) / 2;
for (int indice = 1 ; indice <= lungime ; indice++)
{
if (maxim[0].first > maxim[1].first + termen || (maxim[0].first == maxim[1].first + termen && maxim[0].second < maxim[1].second + 1))
{ maxim[0] = {maxim[0].first + sir[indice] , maxim[0].second}; }
else
{ maxim[0] = {maxim[1].first + termen + sir[indice] , maxim[1].second + 1}; }
if (maxim[1].first < maxim[0].first || (maxim[1].first == maxim[0].first && maxim[0].second < maxim[1].second))
{ maxim[1] = maxim[0]; }
}
if (maxim[1].second <= limita) { rezultat = maxim[1].first - limita * termen; stanga = termen + 1; }
else { dreapta = termen - 1; }
}
cout << rezultat;
return 0;
}
