#include <cstdio>
#include <algorithm>

#define NMAX 10007

using namespace std;

int v[NMAX], Sp[NMAX], Dp[2][NMAX];
int n, k;

void Solve(int st){
    int x = st % 2, Max = 0;
    for(int j = st ; j <= k ; ++j, x = 1 - x, Max = 0)
        for(int i = 1 ; i <= n ; ++i){
            Max = max(Max, Dp[1 - x][i] - Sp[i]);
            Dp[x][i] = max(Sp[i] + Max, Dp[x][i-1]);
        }
}

int main(){
    freopen("ferma.in", "r", stdin);
    freopen("ferma.out", "w", stdout);
    scanf("%d %d", &n, &k);
    for(int i = 1 ; i <= n ; ++i){
        scanf("%d", &v[i]);
        Sp[i] = Sp[i-1] + v[i];
    }
    Solve(1);
    int Anp = max(0, Dp[k & 1][n]);
    for(int i = 1 ; i <= n ; ++i)
        Dp[1][i] = max(Dp[1][i-1], Sp[i]);
    Solve(2);
    for(int i = 1 ; i <= n ; ++i)
        Anp = max(Anp, Dp[k&1][i] + Sp[n] - Sp[i]);
    printf("%d", Anp);
    return 0;
}