#include<cstdio>
#define MAXN 10010
#define MAXK 1010
using namespace std;
int dp[MAXK][MAXN];
int sum[MAXN];
int maximum(int a,int b){
    if(a<b)
        return b;
    return a;
}
int main(){
    freopen("ferma.in","r",stdin);
    freopen("ferma.out","w",stdout);
    int n,k,i,j,value,best,first,answer;
    scanf("%d%d",&n,&k);
    for(i=1;i<=n;i++){
        scanf("%d",&value);
        if(i==1)
            first=value;
        sum[i]=sum[i-1]+value;
    }
    for(i=1;i<=k;i++){
        best=dp[i-1][i-1]-sum[i-1];
        for(j=i;j<=n;j++){
            dp[i][j]=maximum(dp[i][j-1],best+sum[j]);
            best=maximum(best,dp[i-1][j]-sum[j]);
        }
    }
    answer=dp[k][n];
    dp[1][1]=first;
    for(i=2;i<=n;i++)
        dp[1][i]=maximum(dp[1][i-1],sum[i]);
    for(i=2;i<=k;i++){
        best=dp[i-1][i-1]-sum[i-1];
        for(j=i;j<=n;j++){
            dp[i][j]=maximum(dp[i][j-1],best+sum[j]);
            if(i==k)
                answer=maximum(answer,dp[i][j]+sum[n]-sum[j]);
            best=maximum(best,dp[i-1][j]-sum[j]);
        }
    }
    printf("%d",answer);
    return 0;
}