#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define all(v) begin(v), end(v)
#define pi pair<int, int>
#define vi vector<int>
using namespace std;
const int N = 1e5+3;
int n, k, sp[N][17];
int a[N];
vector<int> dp, dp2;
int get(int l, int r){
int lg = __lg(r-l+1);
return max(sp[l][lg], sp[r - (1 << lg) + 1][lg]);
}
void compute(int l, int r, int L, int R){
if(l > r) return ;
int mid = (l+r)>>1;
pi best = {1e9, -1};
for(int k = L; k <= min(mid, R); k++){
best = min(best, make_pair(dp2[k-1] + get(k, mid), k));
}
dp[mid] = best.first;
compute(l, mid-1, L, best.second);
compute(mid+1, r, best.second, R);
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> n >> k;
for(int i = 1; i <= n; i++){
cin >> a[i];
sp[i][0] = a[i];
}
for(int j = 1; (1 << j) <= n; j++){
for(int i = 1; i + (1 << j) - 1 <= n; i++)
sp[i][j] = max(sp[i][j-1], sp[i + (1 << (j-1))][j-1]);
}
dp2.assign(n + 1, 0); dp.assign(n + 1, 0);
for(int i = 1; i <= n; i++){
dp2[i] = get(1, i);
}
dp2[0] = 1e9;
for(int i = 2; i <= k; i++){
compute(1, n, 1, n);
// for(int i = 1; i <= n; i++) cout << dp[i] << " ";
// cout << "\n";
dp[0] = 1e9;
swap(dp2, dp);
}
cout << dp2[n];
return 0;
}
