#include <bits/stdc++.h>
using namespace std;
#define sz(x) (int)x.size()
#define fi first
#define se second
#define mp make_pair
typedef long long lli;
typedef pair<int, int> pii;
const int maxn = 3e5 + 5;
const int lim = 1e9 + 9;
int n, k;
int a[maxn];
lli pref[maxn];
lli sum = 0;
pair<lli, int> dp[maxn];
set<pair<lli, int>> S;
void read_input() {
cin >> n >> k;
for(int i = 1; i <= n; ++i) {
cin >> a[i];
}
}
int calc(lli lambda) {
S.clear();
S.insert(mp(0, 0));
dp[0] = mp(0, 0);
for(int i = 1; i <= n; ++i) {
dp[i] = max(dp[i - 1], mp(S.rbegin()->fi + pref[i] - lambda, S.rbegin()->se + 1));
dp[i] = max(dp[i], mp(dp[i - 1].fi - lambda, dp[i - 1].se + 1));
S.insert(mp(dp[i].fi - pref[i], dp[i].se));
}
return dp[n].se;
}
void solve() {
pref[0] = 0;
for(int i = 1; i <= n; ++i) {
pref[i] = pref[i - 1] + a[i];
}
lli low = -maxn * 1LL * lim, high = maxn * 1LL * lim;
while(low <= high) {
lli mid = (low + high) / 2;
if(calc(mid) >= k) low = mid + 1;
else high = mid - 1;
}
calc(high);
cout << dp[n].fi + high * dp[n].se << '\n';
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
read_input();
solve();
}
