#include <bits/stdc++.h>>

using namespace std;

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

int n,k,i,j,a[10010],last[10],dyn[10010][1010][2];

int main()
{
    f>>n>>k;
    for(i=1; i<=n; i++)
        f>>a[i],a[i]+=a[i-1];
    memset(dyn,-128,sizeof(dyn));
    for(i=1; i<=n; i++)
        dyn[i][1][1]=a[i],dyn[i][0][0]=0;
    dyn[0][0][0]=0;
    last[0]=1;last[1]=0;
    for(int r=1; r<=k; r++)
    {
        last[0]=0;last[1]=0;
        for(i=1; i<=n; i++)
            for(int bi=0; bi<2; bi++)
            {
                if(dyn[i-1][r-1][bi]+a[i]-a[i-1]>dyn[last[bi]][r-1][bi]+a[i]-a[last[bi]])
                    last[bi]=i-1;
                dyn[i][r][bi]=max(dyn[i][r][bi],dyn[last[bi]][r-1][bi]+a[i]-a[last[bi]]);
                dyn[i][r][bi]=max(dyn[i][r][bi],dyn[i-1][r][bi]);
            }
    }
//    for(i=1;i<=n;i++)
//    {
//        for(j=0;j<=k;j++)
//            g<<dyn[i][j][0]<<' ';
//        g<<'\n';
//    }g<<'\n';
//    for(i=1;i<=n;i++)
//    {
//        for(j=0;j<=k;j++)
//            g<<dyn[i][j][1]<<' ';
//        g<<'\n';
//    }g<<'\n';
    int ans=0;
    for(i=1;i<=n;i++)
        ans=max(ans,dyn[i-1][k][1]+a[n]-a[i-1]);
    ans=max(ans,max(dyn[n][k][0],dyn[n][k][1]));
    g<<ans;
    return 0;
}