#include <iostream>
#include <fstream>
#include <deque>

using namespace std;

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

#define nmax 10005
#define Kmax 1005

int n, K, a[2*nmax], dp[Kmax][2*nmax], s[2*nmax];
deque<int> dq;

void citeste(){

    f >> n >> K;
    for(int i=1; i<=n; i++) f >> a[i], s[i] = s[i-1]+a[i];

    for(int i=n+1; i<=2*n; i++) a[i] = a[i-n], s[i] = s[i-1]+a[i];//dublez vectorul pentru a fi circular
//    for(int i=1; i<=2*n; i++) cout << s[i] << " ";
  //  cout << "\n";
}

int afla_poz(){

    int poz = 0;
    int rez = -2000000000;
    dq.clear();
    int dr = 0;
    for(int i=1; i<=2*n; i++){
        while(dq.size() && i-dq.front()+1 > n) dq.pop_front();//scot secventele mai mari ca si n;
        while(dq.size() && s[i] <= s[dq.back()]) dq.pop_back();//am nevoie de cea mai mica secventa
        dq.push_back(i);
        if (rez < s[i] - s[dq.front()]){
            rez = s[i] - s[dq.front()];
            poz = dq.front() + 1;
            dr = i;
        }
    }
    return poz;

}

void rezolva(){

    //dp[i][j] = productivitate maxima din primele j gaini avand i treceri


    int rez = 0;
    int poz = afla_poz();

    for(int i=0; i<=K; i++){
        for(int j=1; j<=n; j++) dp[i][j] = 0;
    }

    dp[1][poz] = max(0, a[poz]);

    for(int i=1; i<=K; i++){//am i treceri
        dq.clear();
        //dq.push_back(0);
        dq.push_back(dp[i-1][poz-1] - s[poz-1]);
        for(int j=poz+1; j<=poz+n-1; j++){
            int X = dp[i-1][j-1] - s[j];
            while(dq.size() && dq.back() <= X) dq.pop_back();
            dq.push_back(X);
            dp[i][j] = max(dp[i][j], dq.front() + s[j]);
/*

            for(int k=j; k>=poz; k--){//incerc fiecare secventa de genul [j,k]; [j,k-1]; .. [j,poz]
                //dp[i][j] = max(dp[i][j], dp[i-1][k-1] - s[k-1]);
                dp[i][j] = max(dp[i][j], dp[i-1][k-1] - s[k-1]);
            }
            dp[i][j] += s[j];
  */
            dp[i][j] = max(dp[i][j], dp[i][j-1]);

        }
    }

    rez = dp[K][poz+n-1];

//    cout << rez << "\n";
    g << rez << "\n";

}

int main(){

    citeste();
    rezolva();

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

    return 0;

}