#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = 1e18;
int N, K;
vector<int> A;
vector<ll> dpPrev, dpCur;
void compute(int k, int L, int R, int optL, int optR) {
if (L > R) return;
int mid = (L + R) >> 1;
pair<ll,int> best = {INF, -1};
ll curMax = 0;
for (int j = min(mid-1, optR); j >= optL; j--) {
curMax = max(curMax, (ll)A[j+1]);
ll val = dpPrev[j] + curMax;
if (val < best.first) best = {val, j};
}
dpCur[mid] = best.first;
int opt = best.second;
compute(k, L, mid-1, optL, opt);
compute(k, mid+1, R, opt, optR);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> N >> K;
A.resize(N+1);
for (int i=1; i<=N; i++) cin >> A[i];
dpPrev.assign(N+1, INF);
dpCur.assign(N+1, INF);
ll curMax = 0;
for (int i=1; i<=N; i++) {
curMax = max(curMax, (ll)A[i]);
dpPrev[i] = curMax;
}
for (int k=2; k<=K; k++) {
compute(k, 1, N, 0, N-1);
dpPrev = dpCur;
fill(dpCur.begin(), dpCur.end(), INF);
}
cout << dpPrev[N] << "\n";
}
