#include<fstream>
#include<cstring>
using namespace std;
 
 
ifstream f("ferma.in");
ofstream g("ferma.out");
int A[1007][10007],n,k,i,j,suma[10007],x,Prod,Maxim1;
inline int maxim(int a,int b){
    if(a<b)
        return b;
    return a;
}
void dinamica(){
    for(i=1;i<=k;++i){
         
        Prod=0;
         
        for(j=1;j<=n;++j){
            A[i][j]=maxim(A[i][j-1],Prod+suma[j]);
            Prod=max(Prod,A[i-1][j]-suma[j]);
        }
    }
     
    Maxim1=A[k][n];
}
void dinamicaCiclu(){
     
         
    memset(A,0,sizeof(A));
    A[1][1]=suma[1];
    for(i=2;i<=n;++i)
        A[1][i]=maxim(A[1][i-1],suma[i]);
     
     
    for(i=2;i<=k;++i){
         
        A[i][1]=suma[1];
        Prod=0;
        for(j=2;j<=n;++j){
            A[i][j]=maxim(A[i][j-1],Prod+suma[j]);
            Prod=max(Prod,A[i-1][j]-suma[j]);
             
        }
         
    }
     
}
int main (){
     
    f>>n>>k;
     
    //A[i][j]= productivitatea maxima pentru i strangeri din primele j sectoare
     
    for(i=1;i<=n;++i){
        f>>x;
        suma[i]=suma[i-1]+x;
    }
     
    dinamica();
    dinamicaCiclu();
    Prod=0;
    for(i=1;i<=n;++i)
        Prod=maxim(Prod,A[k][i-1]-suma[i-1]);
     
    g<<maxim(Maxim1,maxim(A[k][n],Prod+suma[n]));
    return 0;
}