#include <bits/stdc++.h>
#define file ""
#define all(x) x.begin(), x.end()
#define sc second
#define fr first
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const ll inf = 1e18 + 5;
const ll mod = 1e9 + 7;
const int N = 1e5 + 5;
int dx[] = {+1, 0, -1, 0};
int dy[] = {0, +1, 0, -1};
int n, k;
int dp[N][105], a[N];
int main() {
ios_base :: sync_with_stdio(false);
cin.tie(nullptr);
srand(time(nullptr));
cin >> n >> k;
memset(dp, 0x3f, sizeof(dp));
int mx = 0;
for (int i = 1; i <= n; i++) cin >> a[i], mx = max(mx, a[i]), dp[i][1] = mx;
for (int block = 2; block <= k; block++) {
stack<pii> s;
for (int i = 1; i <= n; i++) {
int opt = dp[i - 1][block - 1];
while (!s.empty() && s.top().fr < a[i]) {
opt = min(opt, s.top().sc);
s.pop();
}
if (s.empty() || a[i] + opt < s.top().fr + s.top().sc)
s.push({a[i], opt});
if (i >= block) dp[i][block] = s.top().fr + s.top().sc;
}
}
cout << dp[n][k];
return 0;
}
