#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][Kmax][2],sol=-INF;

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

inline void Dinamic(int st)
{
    int i,j;
    for(i=st;i<=N;++i)
        for(j=1;j<=i && j<=K;++j)
        {
            if(!(i==1 && j==1))
                dp[i][j][0]=max(dp[i-1][j][0],dp[i-1][j][1]);
            dp[i][j][1]=max(dp[i-1][j][1]+v[i],max(dp[i-1][j-1][0]+v[i],dp[i-1][j-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[N][K][0],dp[N][K][1]));
    Initial();
    dp[1][1][1]=v[1];
    Dinamic(2);

    /*for(i=1;i<=N;++i)
    {
        for(j=1;j<=K;++j)
            printf("(%d %d) ",dp[i][j][0], dp[i][j][1]);
        printf("\n");
    }*/

    for(k=1;k<=N;++k)
    {
        x=max(s[N]-s[N-k]+dp[N-k][K][0],s[N]-s[N-k]+dp[N-k][K][1]);
        sol=max(sol,x);
    }
    printf("%d\n", max(sol,0));
    return 0;
}