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

int a[10 * MAX][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(j = 1 ; j <= k ; j++)
    {
        ok = 0;
        for(i = 1 ; i <= n ; i++)
        {
            a[i][j] = max(a[i - 1][j], s[i] + ok);
            ok = max(ok, a[i][j - 1] - s[i]);
            rez = max(rez, a[i][j]);
        }
    }
    for(i = 1 ; i <= n ; i++)
    {
        a[i][1] = max(s[i], a[i - 1][1]);
    }
    for(j = 2 ; j <= k ; j++)
    {
        ok = 0;
        for(i = 1 ; i <= n ; i++)
        {
            a[i][j] = max(a[i - 1][j], s[i] + ok);
            ok = max(ok, a[i][j - 1] - s[i]);
            rez = max(rez, a[i][j]);
        }
    }
    for(i = 1 ; i <= n ; i++)
        rez = max(rez, a[i][k] + s[n] - s[i]);
    fout << rez << "\n";
}