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

using namespace std;

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

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

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