#include <fstream>
#include <algorithm>
using namespace std;

int n, k, s[10001], cit, sol;
int a[1001][10001];

int main()
{
    ifstream f("ferma.in");
    ofstream g("ferma.out");

    f >> n >> k;
    for (int i = 1; i <= n; ++i)
    {
        f >> cit;
        s[i] = s[i - 1] + cit;
    }

    for (int i = 1; i <= k; ++i)
    {
        int var = 0;
        for (int j = 1; j <= n; ++j)
        {
            a[i][j] = max(a[i][j - 1], s[j] + var);
            var = max(var, a[i - 1][j] - s[j]);
        }
    }

    sol = max(sol, a[k][n]);
    for (int i = 1; i <= k; ++i)
        for (int j = 1; j <= n; ++j)
            a[i][j] = 0;

    a[1][1] = s[1];
    for (int i = 2; i <= n; ++i)
        a[1][i] = max(a[1][i - 1], s[i]);

    for (int i = 2; i <= k; ++i)
    {
        a[i][1] = s[1];
        int var = 0;
        for (int j = 2; j <= n; ++j)
        {
            a[i][j] = max(a[i][j - 1], s[j] + var);
            var = max(var, a[i - 1][j] - s[j]);
        }
    }

    int var = 0;
    for (int i = 1; i <= n; ++i)
        var = max(var, a[k][i - 1] - s[i - 1]);

    sol = max(sol, max(a[k][n], var + s[n]));
    g << sol;
    g.close();
}