#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
const int MAXN = 100000;
int a[MAXN+5];
int dp[MAXN+5];
int dpp[MAXN+5];
const int INF = 1000000000;
int main(){
ios_base::sync_with_stdio(false), cin.tie(0);
cout.precision(10);
cout << fixed;
int n, k;
cin >> n >> k;
for(int i=1; i<=n; i++) cin >> a[i];
k--;
for(int i=1; i<=n; i++) dp[i] = max(dp[i-1], a[i]);
dp[0] = INF;
while(k-- > 0){
for(int i=0; i<=n; i++){
dpp[i] = dp[i];
dp[i] = INF;
}
stack <tuple <int, int, int>> st;
for(int i=1; i<=n; i++){
int gmn = dpp[i-1];
while(!st.empty() && get<0>(st.top()) <= a[i]){
gmn = min(gmn, get<2>(st.top()));
st.pop();
}
int rs = INF;
if(!st.empty()) rs = get<1>(st.top());
st.push(make_tuple(a[i], min(rs, gmn + a[i]), gmn));
dp[i] = get<1>(st.top());
}
}
cout << dp[n] << "\n";
return 0;
}
