#include<fstream>
#define INF 1<<30
using namespace std;
int a[2][10001],maxi,n,k,p[10001],sol;
ifstream fin("ferma.in");
ofstream fout("ferma.out");

void din2()
{

    for(int i=1;i<=n;i++)
        a[1][i]=max(p[i],a[1][i-1]);
    for(int i=2;i<=k;i++)
    {
        maxi=a[1-i%2][i-1]-p[i-1];
        for(int j=i;j<=n;j++)
        {
            a[i%2][j]=max(a[i%2][j-1],p[j]+maxi);
            maxi=max(maxi,a[1-i%2][j]-p[j]);
        }
    }
    for(int i=1;i<=n;i++)
    {
        sol=max(sol,a[k%2][i]+p[n]-p[i]);
    }
}

void din1()
{
    for(int i=1;i<=k;i++)
    {
        maxi=a[1-i%2][i-1]-p[i-1];
        for(int j=i;j<=n;j++)
        {
            a[i%2][j]=max(a[i%2][j-1],p[j]+maxi);
            maxi=max(maxi,a[1-i%2][j]-p[j]);
        }
    }
}
void citesc()
{
    fin>>n>>k;
    for(int i=1;i<=n;i++)
    {
        fin>>p[i];
        p[i]+=p[i-1];
    }
}

int main()
{
    citesc();
    din1();
    sol=a[k%2][n];
    din2();
    if(sol<0)
    sol=0;
    fout<<sol;
    return 0;
}