#include <bits/stdc++.h>
#define mp make_pair
#define X first
#define Y second
using namespace std;
typedef long long ll;
typedef pair <int, int> ii;
const int N = 1e5 + 1;
const int K = 101;
const int INF = 1e9;
int n, k, h[N];
int top, dp[K][N];
ii St[N];
int main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n >> k;
for(int i = 1; i <= n; i++)
cin >> h[i];
dp[1][1] = h[1];
for(int i = 2; i <= n; i++)
dp[1][i] = max(dp[1][i - 1], h[i]);
for(int c = 2; c <= k; c++){
top = 0;
h[c - 1] = INF;
dp[c][c - 1] = INF;
St[++top] = mp(c - 1, dp[c - 1][c - 1]);
for(int i = c; i <= n; i++){
while (h[i] >= h[St[top].X]){
St[top - 1].Y = min(St[top - 1].Y, St[top].Y);
top--;
}
dp[c][i] = min(dp[c][St[top].X], St[top].Y + h[i]);
St[++top] = mp(i, dp[c - 1][i]);
}
}
cout << dp[k][n];
return 0;
}
