#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[2][10010][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[1][i][1]=a[i],dyn[0][i][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[(r-1)&1][i-1][bi]+a[i]-a[i-1]>dyn[(r-1)&1][last[bi]][bi]+a[i]-a[last[bi]])
                    last[bi]=i-1;
                dyn[r&1][i][bi]=max(dyn[r&1][i][bi],dyn[(r-1)&1][last[bi]][bi]+a[i]-a[last[bi]]);
                dyn[r&1][i][bi]=max(dyn[r&1][i][bi],dyn[r&1][i-1][bi]);
            }
        memset(dyn[(r+1)&1],-128,sizeof(dyn[(r+1)&1]));
    }
//    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[k&1][i-1][1]+a[n]-a[i-1]);
    ans=max(ans,max(dyn[k&1][n][0],dyn[k&1][n][1]));
    g<<ans;
    return 0;
}