#include<bits/stdc++.h>
using namespace std;

ifstream fin("ferma.in");
ofstream fout("ferma.out");

const int NMAX=10005;

int n,k,a[NMAX],sum[NMAX],dp[NMAX][2],dp1[NMAX][2];
//dp[i][j]=suma maxima care se poate obtine prin alegerea
//a j subsecvente din primele i numere
//dp1[i][j]=dp[i][j] ,dar prima subsecventa incepe cu 1 iar
//a (k+1)-a subcv se termina in n(adica prima e legata cu ultima)

int main()
{
    int i,j,mn,mx,mx1;
    bool ok;
    fin>>n>>k;
    for (i=1;i<=n;i++)
        {
            fin>>a[i];
            sum[i]=sum[i-1]+a[i];
        }
    mn=min(0,a[1]);dp1[1][0]=dp[1][0]=a[1];
    for (i=2;i<=n;i++)
        {
            dp1[i][0]=max(dp1[i-1][0],sum[i]);
            dp[i][0]=max(dp[i-1][0],sum[i]-mn);
            mn=min(mn,sum[i]);
        }
    for (j=2,ok=1;j<=k;j++,ok=1-ok)
        {
            dp[j-1][ok]=dp1[j-1][ok]=-(1<<30);
            mx=dp[j-1][1-ok]-sum[j-1];
            mx1=dp1[j-1][1-ok]-sum[j-1];
            for (i=j;i<=n;i++)
                {
                    dp[i][ok]=max(dp[i-1][ok],sum[i]+mx);
                    dp1[i][ok]=max(dp1[i-1][ok],sum[i]+mx1);
                    mx=max(mx,dp[i][1-ok]-sum[i]);
                    mx1=max(mx1,dp1[i][1-ok]-sum[i]);
                }
        }
    mx=-(1<<30);
    for (i=k;i<n;i++) mx=max(mx,dp1[i][1-ok]-sum[i]);
    dp1[n][ok]=sum[n]+mx;
    mx=max(dp1[n][ok],dp[n][1-ok]);
    if (mx<0) fout<<"0\n";
    else fout<<mx<<"\n";
    return 0;
}