#include <bits/stdc++.h>
//#pragma GCC optimize("Ofast,unroll-loops")
//#pragma GCC target("tune=native")
using namespace std;
const int N = 1e5 + 10, M = 100 + 10, inf = 1e9 + 10, LG = 20;
int n, k, a[N], dp[N][M], dp2[N], mini[N][20], lg[N];
int get_min(int l, int r) {
l = max(l, 0), r = min(r, n);
if (l == r)
return inf;
// cout << l << " " << r << '\n';
return min(mini[l][lg[r - l]], mini[r - (1 << lg[r - l])][lg[r - l]]);
}
void input() {
cin >> n >> k;
for (int i = 0; i < n; i++)
cin >> a[i];
}
void solve() {
for (int i = 2; i < N; i++)
lg[i] = lg[i >> 1] + 1;
int tmp = 0;
for (int i = 0; i < n; i++) {
dp2[i] = i - 1;
while (dp2[i] > -1 && a[dp2[i]] <= a[i])
dp2[i] = dp2[dp2[i]];
if (a[i] > tmp)
tmp = a[i];
dp[i][1] = tmp;
}
for (int j = 2; j <= k; j++) {
for (int i = 0; i < n; i++)
mini[i][0] = dp[i][j - 1];
for (int e = 1; e < LG; e++)
for (int i = 0; i + (1 << e) <= n; i++)
mini[i][e] = min(mini[i][e - 1], mini[i + (1 << (e - 1))][e - 1]);
vector<int> vec, vec2;
vec.push_back(1e9 + 10);
vec2.push_back(1e9 + 10);
for (int i = 0; i < n; i++) {
int p = i - 1;
while (p > dp2[i]) {
p = dp2[p];
vec.pop_back();
vec2.pop_back();
}
vec.push_back(get_min(dp2[i], i) + a[i]);
vec2.push_back(min(vec2.back(), vec.back()));
dp[i][j] = vec2.back();
// for (int x: vec)
// cout << x << ' ';
// cout << '\n';
// cout << i << ' ' << j << ' ' << dp[i][j] << '\n';
}
}
cout << dp[n - 1][k];
}
int main() {
// ios:: sync_with_stdio(0), cin.tie(0), cout.tie(0);
input();
solve();
}
