#include <bits/stdc++.h>
#define F(i, a, b) for(int i = (a); i <= (b); ++i)
#define R(i, a, b) for(int i = (a); i >= (b); --i)
#define N(a) (int)a.size()
#define ll long long
using namespace std;
int n, k, a[100001], dp[100001][101];
stack <pair <int, int>> s;
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n >> k;
F(i, 1, n) cin >> a[i];
memset(dp, 63, sizeof dp);
dp[0][1] = 0;
F(i, 1, n) dp[i][1] = max(dp[i - 1][1], a[i]);
F(j, 2, k) {
while(N(s)) s.pop();
F(i, j, n) {
int min_f = dp[i - 1][j - 1];
while(N(s) && a[s.top().first] <= a[i]) {
min_f = min(min_f, s.top().second);
s.pop();
}
dp[i][j] = min(dp[N(s) ? s.top().first : 0][j], min_f + a[i]);
s.push({i, min_f});
}
}
cout << dp[n][k];
return 0;
}
