#include <fstream>

using namespace std;
ifstream r("ferma.in");
ofstream w("ferma.out");
int x, n, k, sol, ii, maxim, maxim1;
int s[10002], d[2][10002], a[2][10002];
int main()
{
    r>>n>>k;
    for(int i=1; i<=n; i++)
    {
        r>>x;
        s[i]=s[i-1]+x;
        a[0][i]=max(s[i],a[0][i-1]);
    }
    ii=0;
    for(int i=1; i<=k; i++)
    {
        maxim=maxim1=0;
        for(int j=1; j<=n; j++)
        {
            d[ii][j]=max(d[ii][j-1],maxim+s[j]);
            maxim=max(maxim,d[1-ii][j]-s[j]);
        }
        if(i!=1)
        {
            for(int j=1; j<=n; j++)
            {
                a[ii][j]=max(a[ii][j-1],maxim1+s[j]);
                maxim1=max(maxim1,a[1-ii][j]-s[j]);
            }
        }
        ii=1-ii;
    }
    sol=0;
    for(int i=1; i<=n; i++)
    {
        sol=max(sol,d[1-ii][i]);
        sol=max(sol,a[1-ii][i]+s[n]-s[i]);
    }
    w<<sol<<"\n";
    return 0;
}