#include <bits/stdc++.h>
using namespace std;
template<typename T> struct LinkedList;
void attemptMergeNext(LinkedList<long long>& list, int ind);
template<typename T> struct LinkedList{
int frontInd = -1;
int backInd = -1;
struct Node{
int next = -1;
int prev = -1;
int version = 0;
T val;
Node(){}
Node(T val){
this->val = val;
}
};
vector<Node> nodes;
void erase(int ind){
nodes[ind].version++;
if(nodes[ind].next != -1){
nodes[nodes[ind].next].prev = nodes[ind].prev;
}
if(nodes[ind].prev != -1){
nodes[nodes[ind].prev].next = nodes[ind].next;
}
if(frontInd == ind){
frontInd = nodes[ind].next;
}
if(backInd == ind){
backInd = nodes[ind].prev;
}
if(nodes[ind].prev != -1){
attemptMergeNext(*this, nodes[ind].prev);
}
}
void mergeNext(int ind){
assert(nodes[ind].next != -1);
nodes[ind].val += nodes[nodes[ind].next].val;
nodes[ind].version++;
erase(nodes[ind].next);
}
void append(T val){
Node node = Node(val);
int ind = nodes.size();
if(backInd == -1){
frontInd = ind;
}else{
nodes[backInd].next = ind;
node.prev = backInd;
}
backInd = ind;
nodes.push_back(node);
if(node.prev != -1){
attemptMergeNext(*this, node.prev);
}
}
T& front(){
return nodes[frontInd].val;
}
T& back(){
return nodes[backInd].val;
}
Node get(int ind){
return nodes[ind];
}
};
void attemptMergeNext(LinkedList<long long>& list, int ind){
int nextInd = list.nodes[ind].next;
if(nextInd == -1) return;
bool merge = (list.nodes[ind].val == 0 || list.nodes[nextInd].val == 0 || (!((list.nodes[ind].val > 0) ^ (list.nodes[nextInd].val > 0))));
if(merge){
list.mergeNext(ind);
}
}
long long greedySolve(int n, int k, vector<int> inp){
vector<int> a;
for(int i=0; i<n; i++){
if(inp[i] == 0) continue;
a.push_back(inp[i]);
}
if(a.empty()) return 0;
n = a.size();
LinkedList<long long> segments;
segments.append(a.front());
for(int i=1; i<n; i++){
segments.append(a[i]);
}
if(segments.front() < 0){
segments.erase(segments.frontInd);
}
if(segments.frontInd == -1) return 0;
if(segments.back() < 0){
segments.erase(segments.backInd);
}
if(segments.backInd == -1) return 0;
long long ans = 0;
int segCount = 0;
priority_queue<pair<long long, pair<int, int>>> elemsToErase;
int ind = segments.frontInd;
while(ind != -1){
long long val = segments.get(ind).val;
if(val < 0){
elemsToErase.push({val, {ind, segments.get(ind).version}});
}else{
ans += val;
segCount++;
elemsToErase.push({-val, {ind, segments.get(ind).version}});
}
if(segCount > k){
while(true){
pair<long long, pair<int, int>> elem = elemsToErase.top();
elemsToErase.pop();
int node = elem.second.first;
if(segments.get(node).version != elem.second.second) continue;
long long val = segments.get(node).val;
if(val > 0){
ans -= val;
if(segments.get(node).prev != -1){
node = segments.get(node).prev;
segments.mergeNext(node);
}
if(segments.get(node).next != -1){
segments.mergeNext(node);
}
elemsToErase.push({segments.get(node).val, {node, segments.get(node).version}});
}else{
ans += val;
segments.erase(node);
if(segments.get(node).prev != -1){
node = segments.get(node).prev;
}else{
node = segments.frontInd;
}
elemsToErase.push({segments.get(node).val, {node, segments.get(node).version}});
}
break;
}
segCount--;
}
ind = segments.get(ind).next;
}
return ans;
}
long long dpSolve(int n, int k, vector<int> a){
vector<vector<long long>> dp[2];
for(int i=0; i<2; i++){
dp[i] = vector<vector<long long>>(n, vector<long long>(k + 1, 0));
}
dp[1][0][1] = max(0, a[0]);
for(int i=1; i<n; i++){
for(int j=1; j<=k; j++){
dp[0][i][j] = max({dp[0][i][j], dp[0][i-1][j], dp[1][i-1][j]});
dp[1][i][j] = max({dp[1][i][j], dp[0][i-1][j-1] + a[i], dp[1][i-1][j] + a[i]});
}
}
long long bestAns = 0;
for(int i=1; i<=k; i++){
for(int j=0; j<2; j++){
bestAns = max(bestAns, dp[j][n-1][i]);
}
}
return bestAns;
}
void bruteforce(int t){
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
while(t--){
uniform_int_distribution<int> nDist(1, 10);
int n = nDist(rng);
uniform_int_distribution<int> kDist(1, n);
int k = kDist(rng);
vector<int> a(n);
for(int i=0; i<n; i++){
int kDist = a[i];
}
}
}
int main(){
cin.tie(nullptr);
ios_base::sync_with_stdio(false);
int n, k;
cin>>n>>k;
vector<int> a(n);
for(int i=0; i<n; i++){
cin>>a[i];
}
if(n <= 2000 || k == 1){
cout<<dpSolve(n, k, a);
}else{
cout<<greedySolve(n, k, a);
}
}
/*
3 1
2 -1 3
*/
/*
*/
