#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
int read_int(){
int result = 0;
char ch;
ch = getchar();
while (true) {
if (ch >= '0' && ch <= '9') break;
ch = getchar();
}
result = ch-'0';
while (true) {
ch = getchar();
if (ch < '0' || ch > '9') break;
result = result*10 + (ch - '0');
}
return result;
}
typedef long long int64;
const int64 INF = 1e16 + 3;
int n, k;
vector<int> nums;
namespace subtask_3 {
bool approve() {
return n <= 100 && k <= 100;
}
struct SegmentTree {
vector<int64> tree, lazy;
SegmentTree (int n) : tree(n << 2 | 3, INF), lazy(n << 2 | 3, 0) {}
void reload() {
fill(tree.begin(), tree.end(), INF);
fill(lazy.begin(), lazy.end(), 0);
}
void apply(int id, int64 x) {
tree[id] += x;
lazy[id] += x;
}
void push(int id) {
if(lazy[id]) {
apply(id << 1, lazy[id]);
apply(id << 1 | 1, lazy[id]);
lazy[id] = 0;
}
}
void update(int id, int l, int r, int p, int64 x) {
if(l == r) return tree[id] = x, void();
int mid = (l + r) >> 1;
push(id);
if(p <= mid) update(id << 1, l, mid, p, x);
else update(id << 1 | 1, mid + 1, r, p, x);
tree[id] = min(tree[id << 1], tree[id << 1 | 1]);
}
void update(int id, int l, int r, int u, int v, int64 x) {
if(r < u || v < l) return void();
if(u <= l && r <= v) return apply(id, x), void();
int mid = (l + r) >> 1;
push(id);
update(id << 1, l, mid, u, v, x);
update(id << 1 | 1, mid + 1, r, u, v, x);
tree[id] = min(tree[id << 1], tree[id << 1 | 1]);
}
int64 get(int id, int l, int r, int u, int v) {
if(r < u || v < l) return INF;
if(u <= l && r <= v) return tree[id];
int mid = (l + r) >> 1;
push(id);
return min(get(id << 1, l, mid, u, v), get(id << 1 | 1, mid + 1, r, u, v));
}
};
void execute() {
SegmentTree seg(n);
vector<vector<int64>> dp(n + 1, vector<int64>(k + 1, INF));
dp[0][0] = 0;
for(int t = 1; t <= k; t++) {
stack<int> mono;
seg.reload();
for(int i = t; i <= n; i++) {
seg.update(1, t, n, i, dp[i - 1][t - 1]);
while(!mono.empty() && nums[i] > nums[mono.top()]) {
int p = mono.top(); mono.pop();
seg.update(1, t, n, (mono.empty() ? 0 : mono.top()) + 1, p, -nums[p]);
}
seg.update(1, t, n, (mono.empty() ? 0 : mono.top()) + 1, i, nums[i]);
mono.push(i);
dp[i][t] = seg.get(1, t, n, 1, i);
}
}
cout << dp[n][k] << "\n";
}
}
namespace subtask_4 {
bool approve() {
return true;
}
void execute() {
vector<vector<int64>> dp(n + 1, vector<int64>(k + 1, INF));
for(int i = 1, _max = 0; i <= n; i++) {
_max = max(_max, nums[i]);
dp[i][1] = _max;
}
for(int t = 2; t <= k; t++) {
vector<int64> best(n + 1, INF);
stack<int> mono;
for(int i = 1; i <= n; i++) {
while(!mono.empty() && nums[i] > nums[mono.top()]) {
dp[i][t] = min(dp[i][t], dp[mono.top() - 1][k - 1] + nums[i]);
best[i] = min({best[i], best[mono.top()], dp[mono.top()][k - 1]});
dp[i][t] = min(dp[i][t], best[i] + nums[i]);
mono.pop();
}
dp[i][t] = min(dp[i][t], dp[i - 1][t - 1] + nums[i]);
if(!mono.empty()) {
dp[i][t] = min(dp[i][t], dp[mono.top()][t]);
dp[i][t] = min(dp[i][t], dp[mono.top()][t - 1] + nums[i]);
dp[i][t] = min(dp[i][t], dp[mono.top() - 1][t - 1] + nums[mono.top()]);
}
mono.push(i);
}
}
cout << dp[n][k] << "\n";
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
n = read_int();
k = read_int();
nums.resize(n + 1);
for(int i = 1; i <= n; i++) {
nums[i] = read_int();
}
// if(subtask_3::approve()) return subtask_3::execute(), 0;
if(subtask_4::approve()) return subtask_4::execute(), 0;
return 0;
}
