#include <bits/stdc++.h>
#define int long long
using namespace std;
signed main() {
cin.tie(0)->sync_with_stdio(0);
int n, k;
cin >> n >> k;
vector<int> arr(n+2, 0);
vector<vector<int>> dp(k+2, vector<int>(n+2, 1e18));
dp[0][0] = 0;
for(int i=1; i<=n; i++) cin >> arr[i];
for(int i=1; i<=k; i++) {
stack<tuple<int, int, int>> s;
int mn = 0;
dp[i][i] = dp[i-1][i-1] + arr[i];
s.push({i, arr[i], dp[i][i]});
for(int j=i+1; j<=n; j++) {
dp[i][j] = min(dp[i][j], dp[i-1][j-1] + arr[j]);
while(!s.empty() && arr[j] > get<1>(s.top())) {
dp[i][j] = min(dp[i][j], dp[i][get<0>(s.top())] + arr[j] - get<1>(s.top()));
s.pop();
}
if(!s.empty()) {
dp[i][j] = min(dp[i][j], dp[i][get<0>(s.top())]);
}
s.push({j, arr[j], dp[i][j]});
}
}
cout << dp[k][n];
}
