#include <fstream>

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