#include <bits/stdc++.h>
#define fileIO(name) if(fopen(name".inp", "r")) {freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout);}
#define SPEED ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define rall(x) (x).rbegin(), (x).rend()
#define all(x) (x).begin(), (x).end()
#define sqr(x) (x) * (x)
#define eb emplace_back
#define epl emplace
#define lwb lower_bound
#define upb upper_bound
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef long double ldb;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<ll, ll> pll;
typedef pair<ll, int> pli;
typedef pair<int, ll> pil;
typedef pair<int, int> pii;
typedef pair<double, double> pdd;
template<class T1, class T2> bool minimize(T1 &a, T2 b){
return a > b ? a = b, true : false;
}
template<class T1, class T2> bool maximize(T1 &a, T2 b){
return a < b ? a = b, true : false;
}
const int N = 1e5 + 1, K = 101, oo = 1e9 + 10;
int n, k, a[N], dp[K][N];
int main(){
//SPEED;
cin >> n >> k;
for(int i = 1; i <= n; ++i){
cin >> a[i];
}
memset(dp, 0x3f, sizeof dp);
dp[1][0] = 0;
for (int i = 1; i <= n; ++i) dp[1][i] = max(dp[1][i - 1], a[i]);
for(int i = 2; i <= k; ++i){
stack<pii> stk;
for(int j = i; j <= n; ++j){
int MinPrevF = dp[i - 1][j - 1];
while(!stk.empty() && a[stk.top().fi] <= a[j]){
minimize(MinPrevF, stk.top().se);
stk.pop();
}
dp[i][j] = min(dp[i][stk.empty() ? 0 : stk.top().fi], MinPrevF + a[j]);
stk.push({j, MinPrevF});
}
}
cout << dp[k][n];
return 0;
}
