#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
const int K = 105;
const int INF = 1e9;
using pii = pair<int, int>;
#define fi first
#define se second
int n, a[N], k, dp[N][K], l[N];
void cmin(int& x, int y){x = min(x, y);}
int main(){
//freopen("kblocks.inp", "r", stdin);
//freopen("kblocks.out", "w", stdout);
ios::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 <= n; i++)
for (int j = 0; j <= k; j++)
dp[i][j] = INF;
dp[0][0] = 0;
for (int j = 1; j <= k; j++){
stack<pii> st;
for (int i = j; i <= n; i++){
int mn = dp[i - 1][j - 1];
while (!st.empty() && a[st.top().se] <= a[i]){
cmin(mn, st.top().fi);
st.pop();
}
if (st.empty()) l[i] = 0;
else l[i] = st.top().se;
st.emplace(mn, i);
dp[i][j] = min(dp[l[i]][j], mn + a[i]);
}
}
cout << dp[n][k];
}
