#include <bits/stdc++.h>
using namespace std;

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

const int DIM1 = 1e3 + 5;
const int DIM2 = 1e4 + 5;

int D[DIM1][DIM2], S[DIM2], N, K, ans;

void calcDp( int X ) {

    for( int i = X; i <= K; i ++ ) {
        int maxim = D[i - 1][i - 1] - S[i - 1];

        for( int j = i; j <= N; j ++ ) {
            D[i][j] = max( D[i][j - 1], S[j] + maxim );
            maxim = max( maxim, D[i - 1][j] - S[j] );
        }
    }

    return;
}

int main( int argc, const char *argv[] ) {

    in >> N >> K;
    for( int i = 1; i <= N; i ++ ) {
        in >> S[i];
        S[i] += S[i - 1];
    }

    calcDp( 1 );
    ans = max( ans, D[K][N] );

    D[1][1] = S[1];
    for( int i = 2; i <= N; i ++ )
        D[1][i] = max( D[1][i - 1], S[i] );

    calcDp( 2 );
    ans = max( ans, D[K][N] );

    for( int i = K; i <= N; i ++ )
        ans = max( ans, D[K][i] + S[N] - S[i] );

    out << ans;
    return 0;
}