#include <stdio.h>
#define NMAX 10005
#define KMAX 1024
#define Inf 0x3f3f3f3f
int N,K,v[NMAX],a[2][KMAX],b[2][KMAX];
int max(int a,int b) {return a>b?a:b;}
int main()
{
    int i,j,now=1,prev=0,sol;
    freopen("ferma.in","r",stdin);
    freopen("ferma.out","w",stdout);
    scanf("%d %d",&N,&K);
    for (i=1;i<=N;++i) scanf("%d",v+i);
    
    for (i=0;i<=K;++i) a[now][i]=b[now][i]=-Inf;
    a[now][1]=v[1];
    b[now][0]=0;
    for (i=2;i<=N;++i)
    {
        now=i&1;prev=1-now;
        for (j=1;j<=K;++j)
        {
            a[now][j]=v[i]+max(max(a[prev][j],a[prev][j-1]),b[prev][j-1]);
            b[now][j]=max(b[prev][j],a[prev][j]);
        }
    }
    sol=max(a[now][K],b[now][K]);

    now=1;
    for (i=0;i<=K+1;++i) a[now][i]=b[now][i]=-Inf;
    for (i=0;i<=K+1;++i) a[1-now][i]=b[1-now][i]=-Inf;
    a[now][1]=v[1];
    for (i=2;i<=N;++i)
    {
        now=i&1;prev=1-now;
        for (j=1;j<=K+1;++j)
        {
            a[now][j]=v[i]+max(max(a[prev][j],a[prev][j-1]),b[prev][j-1]);
            b[now][j]=max(b[prev][j],a[prev][j]);
        }
    }
    sol=max(sol,a[now][K+1]);
    
    sol=max(sol,0);
    
    printf("%d",sol);
    
    return 0;
}