#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <set>
#include <queue>
#include <deque>

using namespace std;

ifstream f("ferma.in");
ofstream g("ferma.out");

#define nmax 10005
#define Kmax 1005
#define ll long long
#define inf (1<<30)
int n, K, a[nmax], dq[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 bagaDinamica(int linie){
    // merge fara deque eu ma 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=1; j<i; ++j) g << dp[i][j] << " ";
        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;
        }
        //g << "\n";
    }
    //g << "\n";
}

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]);

    bagaDinamica(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
    bagaDinamica(2);
    for(int i=1; i<=n; ++i) Rez = max(Rez, dp[K][i] + sum[n] - sum[i]);
    cout << Rez << "\n";
    g << Rez << "\n";

}

void memo(){
    int sum = sizeof(a) + sizeof(dq) + sizeof(dp) + sizeof(sum) + sizeof(n)*2;

}

int main(){
    citeste();
    rezolva();

    memo();

    f.close();
    g.close();

    return 0;
}