#include <fstream>

using namespace std;

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

const int NMAX=1e4+5, KMAX=1e3+5;
int n, k, ans, v[NMAX], sp[NMAX], maxdp[2][KMAX], maxdp1[2][KMAX], dp[2][KMAX], dp1[2][KMAX];

int main()
{
    in>>n>>k;
    for(int i=1;i<=n;i++)
    {
        in>>v[i];
        sp[i]=sp[i-1]+v[i];
    }
    
    int b=1;
    for(int i=1;i<=n;i++, b^=1)
    {
        for(int j=1;j<=min(k, i);j++)
        {
            dp[b][j]=v[i]+max(dp[b^1][j], maxdp[b^1][j-1]);
            maxdp[b][j]=max(maxdp[b^1][j], dp[b][j]);
            
            if(j>1)
                dp1[b][j]=v[i]+max(dp1[b^1][j], maxdp1[b^1][j-1]);
            else
                dp1[b][j]=v[i]+dp1[b^1][j];
            maxdp1[b][j]=max(maxdp1[b^1][j], dp1[b][j]);
        }
        ans=max(ans, (sp[n]-sp[i])+maxdp1[b][k]);
    }
    ans=max(ans, maxdp[n%2][k]);
    out<<ans;
    return 0;
}