//
// main.cpp
// IZhO14_blocks
//
// Created by KJBS2 on 2015. 2. 23..
// Copyright (c) 2015년 KJBS2. All rights reserved.
//
#include <stdio.h>
#include <stack>
#define MAX_N 101101
#define MAX_K 111
using namespace std;
int N, K;
int Nr[MAX_N];
int Dy[MAX_K][MAX_N];
stack< pair<int, int> > S;
int main() {
scanf("%d%d", &N, &K);
for(int i=1; i<=N; i++) {
scanf("%d", &Nr[i]);
Dy[1][i] = max(Nr[i], Dy[1][i-1]);
}
for(int k=1; k<K; k++) {
while(!S.empty()) S.pop();
for(int i=k+1; i<=N; i++) {
int now = Nr[i];
int block = Dy[k][i-1];
while(!S.empty() && (S.top()).first <= now ) {
if( (S.top()).second < block )
block = (S.top()).second;
S.pop();
}
if(S.empty() || now + block <= ( (S.top()).first + (S.top()).second ) )
S.push( make_pair(now, block) );
Dy[k+1][i] = ( (S.top()).first + (S.top()).second );
// printf("%d %d : <%d %d> %d\n", k+1, i, now, block, Dy[k+1][i]);
}
}
printf("%d\n", Dy[K][N]);
return 0;
}
