#include <bits/stdc++.h>
using namespace std; using ii = pair<int,int>; using ll = long long; using vi = vector<int>;
#define rep(i,a,b) for (auto i = (a); i <= (b); ++i)
#define per(i,a,b) for (auto i = (b); i >= (a); --i)
#define all(x) begin(x), end(x)
#define siz(x) int32_t((x).size())
#define Mup(x,y) (x = max(x,y))
#define mup(x,y) (x = min(x,y))
#define fi first
#define se second
#define pb push_back
#define dbg(...) fprintf(stderr,__VA_ARGS__)
// #define int long long
template <class T, const int N>
struct PURQ {
int n; T t[2*N]; T (*op)(T,T);
void set(int _n, T e, T f(T,T)) { n=_n, fill(t,t+2*n,e), op=f; }
void update(int k, T v) {
assert(0 <= k and k < n);
k += n;
for (t[k] = v; (k /= 2) >= 1; t[k] = op(t[2*k],t[2*k+1]));
}
T query(int a, int b) {
assert(0 <= a and a-1 <= b and b < n);
T l = t[0], r = t[0];
for (a += n, b += n; a <= b; ++a /= 2, --b /= 2) {
if (a&1) l = op(l,t[a]);
if (~b&1) r = op(t[b],r);
}
return op(l,r);
}
};
const ll N = 1e5+3, K = 103;
const int INF = 1e9;
int n, A[N], k;
PURQ<int,N> rmq;
int dp[N][K];
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n >> k;
rmq.set(n+1, -INF, [](int x, int y){ return max(x,y); });
rep(i,1,n) cin >> A[i], rmq.update(i,A[i]);
fill(dp[0],dp[N],INF);
dp[0][0] = 0;
rep(i,1,n) {
rep(j,1,min(k,i)) {
int a=j,b=i,m;
// 단조증가 단조감소
// dp[m-1][k-1] + rmq.query(m,i)
// rmq.query(m,i)=c인 애들 중 가장 인덱스가 작은 위치로 m 옮기기
auto f = [i,j](int x) -> int {
return dp[x-1][j-1] + rmq.query(x, i);
};
auto lb = [i](int x) -> int {
x = rmq.query(x,i);
int a=1, b=i, m;
while (a<=b) {
m=(a+b)/2;
if (rmq.query(m,i)>x) a=m+1;
else b=m-1;
}
assert(rmq.query(a,i) == x);
if (a>1)
assert(rmq.query(a-1,i) > x);
return a;
};
while (a<=b) {
m=(a+b)/2;
if (f(lb(lb(m)-1)) > f(lb(m))) a=m+1;
else b=m-1;
}
mup(dp[i][j], f(max(j,lb(a))));
}
}
cout << dp[n][k];
}
