#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("ferma.in");
ofstream fout("ferma.out");
#define MAX 1008

int a[2][10 * MAX], x[10 * MAX], s[10 * MAX];

int main()
{
    int n, k, i, j, rez, ok;
    fin >> n >> k;
    for(i = 1 ; i <= n ; i++)
    {
        fin >> x[i];
        s[i] = s[i - 1] + x[i];
    }
    rez = 0;
    for(i = 1 ; i <= k ; i++)
    {
        ok = 0;
        for(j = 1 ; j <= n ; j++)
        {
            a[i & 1][j] = max(a[i & 1][j - 1], s[j] + ok);
            ok = max(ok, a[(i - 1) & 1][j] - s[j]);
            rez = max(rez, a[i & 1][j]);
        }
    }
    for(i = 1 ; i <= n ; i++)
    {
        a[1][i] = max(s[i], a[1][i - 1]);
    }
    for(i = 2 ; i <= k ; i++)
    {
        ok = 0;
        for(j = 1 ; j <= n ; j++)
        {
            a[i & 1][j] = max(a[i & 1][j - 1], s[j] + ok);
            ok = max(ok, a[(i - 1) & 1][j] - s[j]);
            rez = max(rez, a[i & 1][j]);
        }
    }
    for(i = 1 ; i <= n ; i++)
        rez = max(rez, a[k & 1][i] + s[n] - s[i]);
    fout << rez << "\n";
}