#include <cstring>
#include <fstream>
#include <algorithm>

using namespace std;

int N, K;
int S[10002];
int Smax[1002][10002];

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

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

    Smax[1][1] = S[1];
    for (int i = 2; i <= N; ++i)
        Smax[1][i] = max(Smax[1][i - 1], S[i]);
    for (int i = 2; i <= K; ++i)
    {
        int maxnow = 0;
        Smax[i][1] = S[1];

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

    int maxnow = 0, result;
    for (int i = 1; i < N; ++i)
        maxnow = max(maxnow, Smax[K][i] - S[i]);
    result = max(maxnow + S[N], Smax[K][N]);

    memset(Smax, 0, sizeof(Smax));
    for (int i = 1; i <= K; ++i)
    {
        int maxnow = 0;
        for (int j = 1; j <= N; ++j)
        {
            Smax[i][j] = max(Smax[i][j - 1], maxnow + S[j]);
            maxnow = max(maxnow, Smax[i - 1][j] - S[j]);
        }
    }

    fout << max(result, Smax[K][N]);

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