#include <fstream>
#include <algorithm>
#define nmax 10005
#define Kmax 1005
using namespace std;
ifstream f("ferma.in"); ofstream g("ferma.out");
int n,K,a[nmax],dp[Kmax][nmax];
int sum[nmax];
void citeste()
{   f>>n>>K;
    for(int i=1; i<=n; ++i) {f>>a[i]; sum[i]=sum[i-1]+a[i];}
}
void Dinamica(int linie)
{   //am nevoie la pasul j de maximul de forma dp[i-1][j2, j2<j]-sum[j2];
    for(int i=linie; i<=K; ++i)
    {   int Max=dp[i-1][i-1]-sum[i-1];
        for(int j=i; j<=n; ++j)
        {   // nu are sens sa fac mai multe strangeri decat am pozitii posibile;
            //deci pornesc de la cazul cnad fac i stangerei de cate o gaina fiecare data
            dp[i][j]=max(dp[i][j-1],Max+sum[j]);
            Max=max(Max,dp[i-1][j]-sum[j]);// pregatesc pentru j+1;
        }
    }
}
void rezolva()
{   // deci in primul rand fac abstractie de faptul ca sirul poate fi circular
    // am asa dp[i][j] = costul maxim obtinut daca fac i stangeri si trec prin primele j gaini
    // ar veni asa dp[i][j] = dp[i-1][j2] + subsecventa cea mai buna ce se termina ep pozitia i;
    // avnad in vedere ca eu fac dp[i][j] = costul maxim obtinut daca iau sau nu iau in considerare pozitai j notez asta cu (1)
    // atunci e ok ca dp[i][j] = dp[i-1][j2] + suma pe intervalul [j2+1..j]; pentru ca sa zicem ca avem cazul :
    // sunt la starea (i, j); si vreua sa continui i-1, j2; doar ca ar fi otpim sa iau (i-1,j2) impreuna nu cu suma de pe j2+1...j ci suma de
    // pe j3..j; unde j3 > j2+1; => pe baza lui (1) ca imi gasea corect profitul maxim la pasul j3 adica la dp[i-1][j3] + suma pe j3+1,j
    // bun acum e n^2 *k trebuie redus la n * k; dp[i][j] = dp[i-1][j2] + S[j] - S[j2]; <=> dp[i][j] = maxim(dp[i-1][j2] - S[j2]) + S[j];
    // => bot baga un deque ca eu am nevoie la pasul de cea mai buna perecehe de forma(dp[i-1][j2] - S[j2]);
    // bun acum faza cu circularitatea : o fac asa oblig ca prima strangere sa inceapa pe pozitia 1
    // iar apoi bag dinamica; la sfarsit o sa am asa : dp[i][j] = costul maxim obtinut avand i strangeri si uitandu-ma la primele j gaini
    // doar ca stiu sigur ca prima strangere il contine pe 1; acum tot ce trebuie sa fac e sa mai adaug la prima strangere fiecare
    // secventa de genul a[k] + a[k+1]...n; cu k = 1,n; aleg maximul de forma (dp[i][j] + sumaPe[j+1..n]);
    Dinamica(1);
    int Rez=dp[K][n];
    //for(int i=0; i<Kmax; ++i) for(int j=0; j<nmax; ++j) dp[i][j] = 0;
    // acum bag cu circularitate
    // imi fixez prima linie a. i. sa fiu sigur ca il iau pe in prima strangere de oua
    dp[1][1]=sum[1];
    for(int i=2; i<=n; ++i) dp[1][i]=max(dp[1][i-1],sum[i]);// adica le iau pe toate 1..i
    Dinamica(2);
    for(int i=1; i<=n; ++i) Rez=max(Rez,dp[K][i]+sum[n]-sum[i]);
    g<<Rez<<"\n";
}
int main()
{   citeste(); rezolva(); g.close(); return 0;}