#include <fstream>
#define VAL 10005
#define SECV 1005
#define INF 1000000000

using namespace std;

ifstream fin("ferma.in");
ofstream fout("ferma.out");

int N, K, i, j, v[VAL];
int ANS, dp[VAL][SECV];
int ans[2][VAL], a, b;

int main()
{
    fin >> N >> K;
    for (i=1; i<=N; i++)
      fin >> v[i];
    ANS=-INF;
    a=1;
    for (j=1; j<=K; j++)
    {
        for (i=1; i<=N; i++)
        {
            dp[i][j]=max(dp[i-1][j], ans[b][i-1])+v[i];
            if (j==1)
              dp[i][j]=max(dp[i][j], v[i]);
            ans[a][i]=max(ans[a][i-1], dp[i][j]);
        }
        ANS=max(ANS, dp[i][K]);
        swap(a, b);
    }
    for (i=1; i<=N; i++)
    {
        dp[i][1]=dp[i-1][1]+v[i];
        ans[0][i]=max(ans[0][i-1], dp[i][1]);
    }
    a=1;
    b=0;
    for (j=2; j<=K+1; j++)
    {
        for (i=1; i<=N; i++)
        {
            dp[i][j]=max(dp[i-1][j], ans[b][i-1])+v[i];
            ans[a][i]=max(ans[a][i-1], dp[i][j]);
        }
        swap(a, b);
    }
    ANS=max(ANS, dp[N][K+1]);
    fout << max(ANS, 0) << '\n';
    fin.close();
    fout.close();
    return 0;
}