#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[2*nmax][Kmax], 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] = numarul maxim de gaini din primele i sectoare avand j treceri


    int rez = 0;
    int poz = afla_poz();
    for(int w=0; w<=n; w++){
        for(int j=1; j<=k; j++) dp[w][j] = 0;
    }

    dp[poz][1] = max(0, a[poz]);
    for(int i=poz+1, cpy=2; i<=n+poz-1; i++, cpy++){
        for(int j=1; j<=k; j++){
            dp[i][j] = dp[i-1][j];
            for(int kk=i, kk2=cpy; kk>=poz; kk--,kk2--){
                dp[i][j] = max(dp[i][j], (s[i]-s[kk-1]) + dp[kk-1][j-1]);
            }
        }
    }

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

    g << rez << "\n";

}

int main(){

    citeste();
    rezolva();

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

    return 0;

}