#include <bits/stdc++.h>
using namespace std;
const long long INF = (long long)4e18;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int N, K;
cin >> N >> K;
vector<int> A(N + 1);
for (int i = 1; i <= N; i++) cin >> A[i];
vector<long long> dp_prev(N + 1, INF), dp_cur(N + 1, INF);
vector<long long> best(N + 1, INF);
vector<int> pre(N + 1, 0);
dp_prev[0] = 0;
for (int k = 1; k <= K; k++) {
for (int i = 1; i <= N; i++) {
int p = i - 1;
while (p > 0 && A[p] <= A[i]) p = pre[p];
pre[i] = p;
dp_cur[i] = dp_prev[i - 1] + A[i];
best[i] = dp_cur[i];
if (pre[i] != 0) {
int j = pre[i];
best[i] = min(best[i], best[j]);
}
int j = i - 1;
while (j > 0 && A[j] <= A[i]) {
best[i] = min(best[i], best[j] - A[j] + A[i]);
j = pre[j];
}
dp_cur[i] = best[i];
}
dp_prev = dp_cur;
fill(dp_cur.begin(), dp_cur.end(), INF);
}
cout << dp_prev[N];
}
