#include <cstdio>
using namespace std;
FILE *in,*out;
int d[2][10001],v[10001],s[10001] ;
int n, k;
inline int max(int x, int y)
{
    if (x>y)
        return x;
    else
        return y;
}
void fct(int x)
{
    int i,j,aux;

    for (i=x;i<=k;++i)
        for (j=1,aux=0;j<n;++j)
        {
            d[i&1][j]=max(d[i&1][j-1],s[j]+aux);
            aux=max(aux,d[!(i&1)][j]-s[j]);
        }
}

int main ()
{
    int sol=0,i;
    in=fopen("ferma.in","rt");
    fscanf (in,"%d %d",&n,&k) ;
    for (i=0;i<n;++i)
        fscanf (in,"%d",&v[i]) ;
    fclose(in);
    for (i = 1,s[0]=v[0];i<n;++i)
        s[i]=s[i-1]+v[i];
    fct(1);
    for (i=0;i<n;++i)
        sol=max(sol,d[k&1][i]) ;
    for (d[1][0]=max(-1,s[0]),i=1;i<n;++i)
        d[1][i]=max(d[1][i-1],s[i]) ;
    fct (2);
    for (i=0;i<n;++i)
        sol=max(sol,d[k&1][i]+s[n-1]-s[i]);
    out=fopen("ferma.out","wt");
    fprintf(out,"%d",sol) ;
    fclose(out);
    return 0;
}