#include <fstream>
using namespace std;
ifstream fin("ferma.in");
ofstream fout("ferma.out");
int n,k,a[10005],dp[1005][1005],sum[10005],ans,i,val,j;
int main()
{
    fin >>n>>k;
    for(i=1;i<=n;i++)
    {
        fin >>a[i];
        sum[i]=sum[i-1]+a[i];
    }
    for(i=1;i<=k;i++)
    {
        val=dp[i-1][i-1]-sum[i-1];
        for(j=i;j<=n;j++)
        {
            dp[i][j]=max(dp[i][j-1],val+sum[j]);
            if (dp[i-1][j]-sum[j]>val) val=dp[i-1][j]-sum[j];
        }
    }
    if (dp[i-1][j]-sum[j]>ans) ans=dp[i-1][j]-sum[j];
    for(i=1;i<=n;i++)
    {
        dp[1][i]=max(dp[1][i-1],sum[i]);
    }
    for(i=2;i<=k;i++)
    {
        val=0;
        dp[i][1]=a[1];
        for(j=2;j<=n;j++)
        {
            dp[i][j]=max(dp[i][j-1],val+sum[j]);
            val=max(val,dp[i-1][j]-sum[j]);
        }
    }
    for(i=k;i<=n;i++)
    {
        if (dp[k][i]+sum[n]-sum[i]>ans) ans=dp[k][i]+sum[n]-sum[i];
    }
    fout <<ans<<'\n';
    return 0;
}