#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[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-1; i++) a[i] = a[i-n], s[i] = s[i-1]+a[i];//dublez vectorul pentru a fi circular

}

int afla_poz(){

    int poz = 0;
    int rez = (1<<29);
    dq.clear();

    for(int i=1; i<=2*n; i++){
        while(dq.size() && i-dq.front() > 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;
        }
    }

    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[cpy][j] = dp[cpy-1][j];
            for(int kk=i, kk2=cpy; kk>=poz+1; kk--,kk2--){
                dp[cpy][j] = max(dp[cpy][j], (s[i]-s[kk-1]) + dp[kk2-1][j-1]);
            }
        }
    }

    rez = dp[n][k];

    g << rez << "\n";

}

int main(){

    citeste();
    rezolva();

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

    return 0;

}