#include <cstdio>
#include <algorithm>
#define Nmax 10005
#define Kmax 1005
#define INF 2000000000

using namespace std;

int v[Nmax],s[Nmax],N,K,dp[2][Nmax][2],sol;

inline void Initial()
{
    int i,j;
    for(i=0;i<=1;++i)
        for(j=1;j<=N;++j)
            dp[i][j][0]=dp[i][j][1]=-INF;
}

inline void Dinamic(int st)
{
    int i,j,c,c1;
    for(j=st;j<=K;++j)
    {
        c=j%2; c1=(j+1)%2;
        for(i=1;i<=N;++i)
            dp[c][i][0]=dp[c][i][1]=-INF;
        for(i=j;i<=N;++i)
        {
            if(!(i==1 && j==1))
                dp[c][i][0]=max(dp[c][i-1][0],dp[c][i-1][1]);
            dp[c][i][1]=max(dp[c][i-1][1]+v[i],max(dp[c1][i-1][0]+v[i],dp[c1][i-1][1]+v[i]));
        }
    }
}

int main()
{
    int i,j,k,x;
    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]);
        s[i]=s[i-1]+v[i];
    }
    Initial();
    Dinamic(1);
    sol=max(sol,max(dp[K%2][N][0],dp[K%2][N][1]));
    Initial();
    for(i=1;i<=N;++i)
    {
        if(i!=1)
            dp[1][i][0]=max(dp[1][i-1][0],dp[1][i-1][1]);
        dp[1][i][1]=s[i];
    }
    Dinamic(2);
    for(k=1;k<=N;++k)
    {
        x=max(s[N]-s[N-k]+dp[K%2][N-k][0],s[N]-s[N-k]+dp[K%2][N-k][1]);
        sol=max(sol,x);
    }
    printf("%d\n", sol);
    return 0;
}