#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
const int N = 1e5 + 5;
const int inf = 0x3f3f3f3f3f3f3f3f;
int a[N],n,k,dp[105][N];
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n >> k;
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 0; i <= k; i++)
for (int j = 0; j <= n; j++) dp[i][j] = inf;
int Max = 0;
for (int i = 1; i <= n; i++) {
Max = max(Max,a[i]);
dp[1][i] = Max;
}
for (int i = 2; i <= k; i++) {
stack<pii>st;
for (int j = 1; j <= n; j++) {
int Min = dp[i - 1][j - 1];
while (!st.empty() && a[st.top().fi] < a[j]) {
Min = min(Min,st.top().se);
st.pop();
}
if (st.empty() || a[j] + Min < a[st.top().fi] + st.top().se)
st.push(mp(j,Min));
if (j >= i) dp[i][j] = a[st.top().fi] + st.top().se;
}
}
cout << dp[k][n] << "\n";
}
