/*
https://oj.uz/problem/view/NOI19_feast
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef pair<ll, ll> pll;
typedef vector<pll> vpll;
typedef vector<vpll> vvpll;
typedef vector<bool> vb;
#define fi first
#define se second
const ll INSUB = 1ll, NOTSUB = 0ll;
/*
Find the maximal value of sum of all subarrays minus y * number subarrays
*/
pll solve_lambda(const vll& a, ll n, ll y) {
vvpll dp(n, vpll(2ll, {0ll, 0ll}));
dp[0ll][INSUB] = {a[0ll] - y, 1ll};
for(ll i = 1ll; i < n; i++) {
dp[i][INSUB] = {dp[i - 1ll][INSUB].fi + a[i], dp[i - 1ll][INSUB].se};
pll insub_cand = {dp[i - 1ll][NOTSUB].fi + a[i] - y, dp[i - 1ll][NOTSUB].se + 1ll};
if(insub_cand > dp[i][INSUB]) dp[i][INSUB] = insub_cand;
dp[i][NOTSUB] = {dp[i - 1ll][NOTSUB].fi, dp[i - 1ll][NOTSUB].se};
pll notsub_cand = {dp[i - 1ll][INSUB].fi, dp[i - 1ll][INSUB].se};
if(notsub_cand > dp[i][NOTSUB]) dp[i][NOTSUB] = notsub_cand;
}
if(dp[n - 1ll][INSUB] > dp[n - 1ll][NOTSUB]) return dp[n - 1ll][INSUB];
return dp[n - 1ll][NOTSUB];
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
ll n, k;
cin >> n >> k;
vll a(n, 0ll);
for(ll& v : a) cin >> v;
ll low = -1ll, hi = 1e13;
ll low_val = 0ll;
while(hi - low > 1ll) {
ll mid = (hi + low) >> 1ll;
auto [opt_val, opt_k] = solve_lambda(a, n, mid);
if(opt_k >= k) {
low = mid;
low_val = opt_val;
}
else {
hi = mid;
}
}
cout << low_val + k * low << endl;
return 0;
}
