#include <fstream>
using namespace std;

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

const int MAXN = 10005;
const int MAXK = 1005;
int N, K;
int sum[MAXN];
int D[MAXN][MAXK];
int rez;

void Read();
void Solve();

int main()
{
    Read();
    Solve();

    fout << rez << '\n';

    fin.close();
    fout.close();
    return 0;
}

void Read()
{
    int i, x;

    fin >> N >> K;
    for ( i = 1; i <= N; i++ )
    {
        fin >> x;
        sum[i] = sum[i - 1] + x;
    }
}

void Solve()
{
    int i, j;
    int x;

    for ( i = 1; i <= K; i++ )
    {
        x = D[i - 1][i - 1] - sum[i - 1];

        for ( j = i; j <= N; j++ )
        {
            D[i][j] = max( D[i][j - 1], x + sum[j] );
            x = max( x, D[i - 1][j] - sum[j] );
        }
    }

    rez = D[K][N];

   /* for ( i = 1; i <= K; i++ )
    {
        for ( j = 1; j <= N; j++ )
            fout << D[i][j] << ' ';
        fout << '\n';
    }   */

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

    for ( i = 2; i <= K; i++ )
    {
        x = D[i - 1][i - 1] - sum[i - 1];

        for ( j = i; j <= N; j++ )
        {
            D[i][j] = max( D[i][j - 1], x + sum[j] );

            if ( i == K && D[i][j] + sum[N] - sum[j] > rez )
                rez = D[i][j] + sum[N] - sum[j];

            x = max( x, D[i - 1][j] - sum[j] );
        }
    }

  /*  for ( i = 1; i <= K; i++ )
    {
        for ( j = 1; j <= N; j++ )
            fout << D[i][j] << ' ';
        fout << '\n';
    }   */
}