#include<bits/stdc++.h>
#define taskname "C"
using namespace std;
typedef long long ll;
template<class T>void minimize(T& a, T b){
if(a > b){
a = b;
}
}
template<class T>void maximize(T& a, T b){
if(a < b){
a = b;
}
}
const int lim = 3e5 + 5;
const ll INF = 1e18;
int n, k, a[lim];
namespace sub1{
void solve(){
cout << accumulate(a + 1, a + n + 1, 0LL);
}
}
namespace sub3{
void solve(){
ll sum = 0, min_sum = 0, ans = 0;
for(int i = 1; i <= n; i++){
maximize(ans, (sum += a[i]) - min_sum);
minimize(min_sum, sum);
}
cout << ans;
}
}
namespace sub45{
void solve(){
vector<vector<ll>>dp(n + 1, vector<ll>(k + 1, -INF));
dp[0][0] = 0;
for(int i = 1; i <= n; i++){
dp[i] = dp[i - 1];
ll sum = 0;
for(int j = i; j > 0; j--){
sum += a[j];
for(int t = 1; t <= k; t++){
maximize(dp[i][t], dp[j - 1][t - 1] + sum);
}
}
}
cout << *max_element(dp[n].begin(), dp[n].end());
}
}
namespace sub267{
pair<ll, int>dp[lim][2];
void solve(){
dp[0][0] = make_pair(0, 0);
dp[0][1] = make_pair(-INF, 0);
function<pair<ll, int>(ll)>get = [&] (ll lambda){
for(int i = 1; i <= n; i++){
dp[i][0] = max(dp[i - 1][0], dp[i - 1][1]);
dp[i][1] = max(make_pair(dp[i - 1][0].first + a[i] - lambda, dp[i - 1][0].second + 1), make_pair(dp[i - 1][1].first + a[i], dp[i - 1][1].second));
}
return max(dp[n][0], dp[n][1]);
};
ll low = 1, high = INF, best_lambda = 0;
while(low <= high){
ll mid = (low + high) >> 1LL;
if(get(mid).second >= k){
low = (best_lambda = mid) + 1;
}
else{
high = mid - 1;
}
}
cout << get(best_lambda).first + best_lambda * k;
}
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
if(fopen(taskname".inp", "r")){
freopen(taskname".inp", "r", stdin);
}
cin >> n >> k;
for(int i = 1; i <= n; i++){
cin >> a[i];
}
if(*min_element(a + 1, a + n + 1) > -1){
sub1::solve();
}
else if(k == 1){
sub3::solve();
}
else if(max(n, k) <= 300){
sub45::solve();
}
else{
sub267::solve();
}
}
