#include <cstdio>

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;
    freopen("ferma.in","r",stdin);
    freopen("ferma.out","w",stdout);

    scanf ("%d %d",&n,&k) ;
    for (i=0;i<n;++i)
        scanf ("%d",&v[i]) ;

    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]);

    printf("%d",sol) ;

    return 0;
}