# include <cstdio>

const char *FIN = "ferma.in", *FOU = "ferma.out" ;
const int MAX = 10005 ;

int dp[2][MAX], A[MAX], B[MAX] ;
int N, K, sol ;

inline int max (int A, int B) {
    return (A > B ? A : B) ;
}

void doit (int poz) {
    for (int i = poz; i <= K; ++i) {
        for (int j = 1, maxim = 0; j < N; ++j) {
            dp[i & 1][j] = max (dp[i & 1][j - 1], B[j] + maxim) ;
            maxim = max (maxim, dp[!(i & 1)][j] - B[j]) ;
        }
    }
}

int main (void) {
    freopen (FIN, "r", stdin) ;

    scanf ("%d %d", &N, &K) ;
    for (int i = 0; i < N; ++i)
        scanf ("%d", A + i) ;
    for (int i = 0; i < N; ++i)
        B[i] = (i ? B[i - 1] : 0) + A[i] ;
    doit (1) ;
    for (int i = 0; i < N; ++i)
        sol = max (sol, dp[K & 1][i]) ;
    dp[1][0] = B[0] ;
    for (int i = 0; i < N; ++i)
        dp[1][i] = max (i ? dp[1][i - 1] : -1, B[i]) ;
    doit (2) ;
    for (int i = 0; i < N; ++i)
        sol = max (sol, dp[K & 1][i] + B[N - 1] - B[i]) ;
    fprintf (fopen (FOU, "w"), "%d", sol) ;
}