#include<cstdio>
#include<algorithm>
using namespace std;
int v[10077],i,j,n,m,k,l,sp[10077],a[1077][10077];
int INF=0x3f3f3f3f;
int main ()
{
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]);
    sp[i]=sp[i-1]+v[i];
    }
for(i=1;i<=k;i++)
    a[i][0]=-INF;
a[1][1]=v[1];
for(i=1;i<=k;i++)
    {
    int best=a[i-1][0];
    for(j=1+(i==1);j<=n;j++)
        {
        a[i][j]=max(a[i][j-1],best)+v[j];
        best=max(best,a[i-1][j]);
        }
    }
int maxim=0;
for(i=1;i<=n;i++)
    maxim=max(maxim,a[k][i]);
for(i=1;i<=n;i++)
    a[0][i]=-INF;
for(i=1;i<=k;i++)
    {
    int best=a[i-1][0];
    for(j=1+(i==1);j<=n;j++)
        {
        a[i][j]=max(a[i][j-1],best)+v[j];
        best=max(best,a[i-1][j]);
        }
    }
for(i=1;i<=n;i++)
    a[k][i]=max(a[k][i-1],a[k][i]);
for(i=1;i<=n;i++)
    maxim=max(maxim,a[k][i]+sp[n]-sp[i]);
printf("%d",maxim);
return 0;
}