#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = a; i<= b; ++i)
#define FORD(i, a, b) for (int i = a; i>=b; --i)
#define REP(i, a) for (int i = 0; i<a; ++i)
#define DEBUG(x) { cerr << #x << " = " << x << endl; }
#define Arr(A, l, r) { cerr << #A << " = "; FOR(_, l, r) cerr << A[_] << ' '; cerr << endl; }
#define N 100100
#define pp pair<int, int>
#define next __next
#define prev __prev
#define __builtin_popcount __builtin_popcountll
#define bit(S, i) (((S) >> i) & 1)
#define IO cin.tie(NULL);cout.tie(NULL);
#define taskname "Test"
using namespace std;
template<class X, class Y> inline void Max(X &x, Y y) { x = x > y ? x : y; }
template<class X, class Y> inline void Min(X &x, Y y) { x = x < y ? x : y; }
/*
dp[i][j] = min(dp[i - 1][k] + RMQ[k + 1][j]);
*/
int n, k, a[N];
int dp[111][N];
stack<int> st;
int main() {
IO;
scanf("%d %d", &n, &k);
FOR(i, 1, n) scanf("%d", &a[i]);
int mx = -1;
FOR(i, 1, n) Max(mx, a[i]), dp[1][i] = mx;
FOR(j, 2, k) {
while (!st.empty()) st.pop();
st.push(j - 1);
//dp[j][j] = dp[j - 1][j - 1] + a[j];
FOR(i, j, n) {
int best = 1e9;
while (!st.empty() && a[st.top()] <= a[i]) {
if (st.top() != j - 1) Min(best, dp[j][st.top()] + a[i] - a[st.top()]);
Min(best, dp[j - 1][st.top()] + a[i]);
st.pop();
}
if (!st.empty()) {
if (st.top() != j - 1) Min(best, dp[j][st.top()]);
Min(best, dp[j - 1][st.top()] + a[i]);
}
else Min(best, dp[j - 1][j - 1] + a[i]);
dp[j][i] = best;
// cerr << j << ' ' << i << ' ' << best << endl;
st.push(i);
}
}
printf("%d", dp[k][n]);
}
