#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;
string S;
int poz;

void citeste_buf(int &nr){

    nr = 0;
    for(; (S[poz]<'0' || S[poz]>'9') && S[poz]!='-'; poz++);
    int semn = 1;
    if (S[poz] == '-') semn = -1, poz++;
    for(; S[poz]>='0' && S[poz]<='9'; poz++){
        nr = nr * 10 + (S[poz] - '0');
    }

    nr = nr * semn;

}

void citeste(){

    //f >> n >> K;
    getline(f,S);
    poz = 0;
    citeste_buf(n);
    citeste_buf(K);

    S.clear();
    poz = 0;
    getline(f,S);
    for(int i=1; i<=n; i++){
        int x = 0;
        citeste_buf(x);
        a[i] = x;
        //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(dp[i-1][poz-1] - s[poz-1]);
        for(int j=poz+1; j<=poz+n-1; j++){
            dp[i][j] = dp[i][j-1];
            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]);
        }
    }

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

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

}

int main(){

    citeste();
    rezolva();

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

    return 0;

}