#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

int n, K, a[nmax], dq[nmax], dp[nmax][Kmax];
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 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]);

    dp[1][0] = max(0, a[1]);
    for(int i=1; i<=K; ++i){
        int st = 1; int dr = 0;// fac deque-ul de mana
        dq[++dr] = dp[i-1][i-1] - sum[i-1];// il bag pe i-1 pentru al face pe i

        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] = dp[i][j-1];// nu iau in considerare gaina j;
            if (st <= dr) dp[i][j] = max(dp[i][j], dq[st] + sum[j]);

            int Cost = dp[i-1][j] - sum[j];// pregatesc pentru j+1;
            while(st <= dr && dq[dr] <= Cost) --dr;
            dq[++dr] = Cost;
        }
    }
    cout << dp[K][n] << "\n";// asta e fara circularitate
    g << dp[K][n] << "\n";
}

void memo(){
    int sum = sizeof(a) + sizeof(dq) + sizeof(dp) + sizeof(sum) + sizeof(n)*2;
    //cout << sum / 1024 << "\n";
}

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

    memo();

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

    return 0;
}