#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<ll> a, b;
ll res;
ll solve(ll pun)
{
res = 0;
ll last = -pun;
ll seg_cnt = 0;
for (auto n : b)
{
if (n > 0)
{
last += n;
continue;
}
if (n < -pun)
{
if (last > 0)
{
res += last;
seg_cnt++;
}
last = -pun;
}
else
{
last += n;
}
if (last < -pun)
last = -pun;
//cerr << last << ' ' << res << '\n';
}
if (last > 0)
{
res += last;
seg_cnt++;
}
return seg_cnt;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
ll N, K;
cin >> N >> K;
a = vector<ll>(N);
for (int i = 0; i < N; i++)
cin >> a[i];
{
ll sum = a[0];
for (int i = 1; i < N; i++)
{
if ((a[i-1] ^ a[i]) < 0)
{
b.push_back(sum);
sum = 0;
}
sum += a[i];
}
if (sum != 0)
b.push_back(sum);
}
ll l = 0ll;
ll r = 1000000000000000000ll;
while (l < r)
{
ll c = (l + r) / 2ll;
if (solve(c) > K)
l = c + 1;
else
r = c;
}
solve(l);
cout << res + K * l << '\n';
return 0;
}
