#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, 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-1, arr[i], dp[i][i]});
for(int j=i; j<=n; j++) {
while(!s.empty() && arr[j] >= get<1>(s.top())) s.pop();
if(s.empty()) {
dp[i][j] = dp[i-1][i-1] + arr[j];
s.push({i-1, arr[j], dp[i][j]});
} else {
dp[i][j] = min(dp[i-1][get<0>(s.top())] + arr[j], get<2>(s.top()));
s.push({get<0>(s.top()), arr[j], dp[i][j]});
}
}
}
cout << dp[k][n];
}
