#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define fi first
#define se second
int N, K;
int A[100100];
int dp[100100][110];
stack<pii> st;
int maks;
// dp[n][1] = max(a[1..n]);
int main () {
cin >> N >> K;
for(int i=1; i<=N; i++) {
cin >> A[i];
maks = max(maks, A[i]);
dp[i][1] = maks;
}
for(int k=2; k<=K; k++) {
while(!st.empty()) st.pop();
for(int n=1; n<=N; n++) {
if (n<k) dp[n][k] = 1e9;
else {
int mins = dp[n-1][k-1];
while(!st.empty() && A[st.top().fi] <= A[n]) {
mins = min(mins, st.top().se);
st.pop();
}
dp[n][k] = mins+A[n];
if (!st.empty())
dp[n][k] = min(dp[n][k], dp[st.top().fi][k]);
st.push({n,mins});
}
}
}
cout << dp[N][K] << endl;
}
