#include <bits/stdc++.h>

using namespace std;

ifstream fin("ferma.in");
ofstream fout("ferma.out");

const int nmax = 10005, inf = 2000000000, kmax = 1005;
int n, k, v[nmax], dp[2][kmax][2], dp2[2][kmax][2], sum[nmax];


int main(){
    fin >> n >> k;
    for (int i = 1; i <= n; ++i){
        fin >> v[i];
        sum[i] = sum[i - 1] + v[i];
    }
    for (int i = 1; i <= k; ++i){
        dp[(n + 1) % 2][i][0] = dp[(n + 1) % 2][i][1] = -inf;
        dp2[(n + 1) % 2][i][0] = -inf;
    }
    int maxim = -inf;
    for (int index = n; index >= 1; --index){
        dp2[index % 2][0][0] = dp2[index % 2][0][1] = -inf;
        for (int cnt = 1; cnt <= k; ++cnt){
            for (int p = 0; p <= 1; ++p){
                if (p){
                    dp[index % 2][cnt][p] = max(dp[index % 2][cnt - 1][0], v[index] + dp[(index + 1) % 2][cnt][1]);
                    dp2[index % 2][cnt][p] = max(dp2[index % 2][cnt - 1][0], v[index] + dp2[(index + 1) % 2][cnt][1]);
                }
                else{
                    dp[index % 2][cnt][p] = max(dp[(index + 1) % 2][cnt][p], v[index] + dp[(index + 1) % 2][cnt][1]);
                    dp2[index % 2][cnt][p] = max(dp2[(index + 1) % 2][cnt][p], v[index] + dp2[(index + 1) % 2][cnt][1]);
                }
            }
        }
        maxim = max(maxim, dp[index % 2][k][0]);
        maxim = max(maxim, sum[index] + dp2[(index + 1) % 2][k][0]);
    }
    if (maxim < 0){
        maxim = 0;
    }
    fout << maxim;
    return 0;
}