#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e2+5;
const int maxn=1e5+5;
int n,k,a[maxn];
ll dp[N][maxn];
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> k;
for(int i = 1;i <= n;i++) cin >> a[i];
for(int i = 0;i <= k;i++)
for(int j = 0;j <= n;j++) dp[i][j] = 1e18;
dp[1][1] = a[1];
for(int i = 2;i <= n;i++) dp[1][i] = max(dp[1][i-1],1ll*a[i]);
for(int i = 2;i <= k;i++){
stack<pair<int,ll>>s;
for(int j = i;j <= n;j++){
ll jog = dp[i-1][j-1];
while(!s.empty() and a[s.top().first] <= a[j]){
jog = min(jog,s.top().second);
s.pop();
}
ll tmp = 0;
if(!s.empty()) tmp = s.top().first;
dp[i][j] = min(dp[i][tmp],jog+a[j]);
s.push({j,jog});
}
}
// for(int i = 2;i <= n;i++){
// cout<<dp[2][i]<<' ';
// }
cout<<dp[k][n];
}
