#include<fstream>
using namespace std;
ifstream f("ferma.in");
ofstream g("ferma.out");
int n,k,val,i,j,val0,a[5<<11],s[5<<11],din[1<<11][5<<11];
void calc(int i,int j)
{
    din[i][j]=max(val+s[j],din[i][j-1]);
    val=max(val,din[i-1][j]-s[j]);
}
int main()
{
    f>>n>>k;
    for(i=1;i<=n;++i)
    {
        f>>a[i];
        s[i]=s[i-1]+a[i];
    }
    for(i=1;i<=k;++i)
    {
        val=0;
        for(j=1;j<=n;++j)
          calc(i,j);
    }
    val0=din[k][n];
    for(i=1;i<=n;++i)
      din[1][i]=max(din[1][i-1],s[i]);
    for(i=2;i<=k;++i)
    {
        val=0;
        din[i][1]=s[1];
        for(j=2;j<=n;++j)
          calc(i,j);
    }
    val=0;
    for(i=1;i<n;++i)
      val=max(val,din[k][i]-s[i]);
    g<<max(val0,val+s[n]);
    return 0;
}