#include <bits/stdc++.h>
#define lsb(x) (x & (-x))
#define ll long long
#define ull unsigned long long
#define ld long double
// 217
// 44
using namespace std;
const int INF = 1e9;
const int MAXN = (int) 1e5;
const int MAXK = 100;
int dp[MAXN + 1][MAXK + 1];
int arr[MAXN + 1];
int stk[MAXN + 1];
int best[MAXN + 1], mn_dp[MAXN + 1];
int main() {
//ifstream cin("A.in");
//ofstream cout("A.out");
int i, j, n, k;
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> n >> k;
for(i = 1; i <= n; i++) {
cin >> arr[i];
}
for(i = 1; i <= n; i++) {
dp[i][1] = max(dp[i - 1][1], arr[i]);
}
dp[0][1] = INF;
for(j = 2; j <= k; j++) {
int sz = 0;
dp[0][j] = best[0] = INF;
for(i = 1; i <= n; i++) {
int mn = INF;
while(sz > 0 && arr[i] >= arr[stk[sz]]) {
mn = min(mn, mn_dp[sz]);
sz--;
}
stk[++sz] = i;
best[sz] = min(best[sz - 1], min(mn, dp[stk[sz - 1]][j - 1]) + arr[i]);
mn_dp[sz] = min(mn, dp[i][j - 1]);
dp[i][j] = best[sz];
}
}
cout << dp[n][k];
//cin.close();
//cout.close();
return 0;
}
