// #pragma comment(linker, "/stack:200000000")
// #pragma GCC optimize("Ofast")
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4")
// #pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")
// #define _GLIBCXX_DEBUG
// #define _GLIBCXX_DEBUG_PEDANTIC
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
#include <array>
#include <numeric>
#include <queue>
#include <deque>
#include <cmath>
#include <climits>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// #include <ext/rope>
// using namespace __gnu_pbds;
// using namespace __gnu_cxx;
using namespace std;
const int MOD = 998244353;
const long double PI = 3.141592653589793;
using ll = long long;
const ll INF = 1e18;
#define int ll
// template<typename T>
// using ordered_set = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
// template<typename K, typename V>
// using hash_table = cc_hash_table<K, V, hash<K>>;
template<typename T>
using graph = vector<vector<T>>;
template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
for (auto& i: a) {
in >> i;
}
return in;
}
template<typename T>
ostream& operator<<(ostream& out, vector<T>& a) {
for (auto& i: a) {
out << i << " ";
}
return out;
}
ll fast_pow(ll a, ll b, ll mod) {
if (b == 0)
return 1;
if (b % 2) {
return (1ll * a * fast_pow(a, b - 1, mod)) % mod;
}
ll k = fast_pow(a, b / 2, mod);
return (1ll * k * k) % mod;
}
ll fast_pow(ll a, ll b) {
if (b == 0)
return 1;
if (b % 2) {
return (1ll * a * fast_pow(a, b - 1));
}
ll k = fast_pow(a, b / 2);
return (1ll * k * k);
}
int n, k;
vector<int> a;
pair<int, int> calc(int L) {
vector<int> dp(n), c(n);
int cnt = 0;
int mx = 0;
int mx_dp = 0;
int cnt_dp = 0;
for (int i = 0; i < n; i++) {
dp[i] = a[i] - L + mx;
c[i] = cnt + 1;
if (mx_dp > dp[i]) {
dp[i] = mx_dp;
c[i] = cnt_dp;
}
if (dp[i] > mx_dp) {
mx_dp = dp[i];
cnt_dp = c[i];
}
if (mx <= -a[i] + mx_dp) {
mx = -a[i] + mx_dp;
cnt = cnt_dp;
}
}
return {dp.back(), c.back()};
}
void solve() {
cin >> n >> k;
a.resize(n);
cin >> a;
int cnt = 0, sum = 0;
bool f = 0;
for (int i : a) {
if (i > 0) {
f = 1;
sum += i;
} else if (i < 0) {
cnt += f;
f = 0;
}
}
cnt += f;
if (cnt <= k) {
cout << sum << "\n";
return;
}
for (int i = 1; i < n; i++)
a[i] += a[i - 1];
int l = 0;
int r = INF;
while (r - l > 1) {
int mid = (r + l) / 2;
if (calc(mid).second > k) {
l = mid;
} else {
r = mid;
}
}
// cerr << calc(0).second <<" " << calc(0).first << endl;
// return;
// cerr << r << " " << calc(r).second << endl;
cout << calc(r).first + k * r;
// for (int L = -5; L <= 15; L++) {
// cerr << calc(L).second << " ";
// }
}
int32_t main(int32_t argc, const char * argv[]) {
cin.tie(0);
cout.tie(0);
ios_base::sync_with_stdio(0);
// insert code here...
int tt= 1;
// std::cin >> tt;
while (tt--) {
solve();
}
return 0;
}
