#include<fstream>
using namespace std;
int a[2][10001],maxi[2][10001],n,k,p[10001],sol;
ifstream fin("ferma.in");
ofstream fout("ferma.out");
void citire()
{
    fin>>n>>k;
    for(int i=1;i<=n;i++)
    {
        fin>>p[i];
        p[i]+=p[i-1];
    }
}

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

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

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

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