#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2")
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
#include <cstdint>
const int BULAN = 40;
int x, p;
int arr[100005];
int sp_tb[17][100005];
uint32_t dp[105][100005];
void build_sparse_table() {
for (int l = 1; l < 17; l++) {
for (int i = 1; i+(1<<l)-1 <= x; i++) {
sp_tb[l][i] = std::max(sp_tb[l-1][i], sp_tb[l-1][i+(1<<(l-1))]);
}
}
}
inline int max_query(int l, int r) {
int lvl = 31-__builtin_clz(r-l+1);
return std::max(sp_tb[lvl][l], sp_tb[lvl][r-(1<<lvl)+1]);
}
void calculate_dp() {
if (1LL*x*x*p<=50'000'000) {
dp[1][0] = 0x3f3f3f3f;
for (int i = 1; i <= x; i++) {
dp[1][i] = max_query(1,i);
}
for (int k = 2; k <= p; k++) {
for (int i = 0; i < k; i++) {
dp[k][i] = 0x3f3f3f3f;
}
for (int i = k; i <= x; i++) {
dp[k][i] = 0x3f3f3f3f;
for (int j = k; j <= i; j++) {
dp[k][i] = std::min(dp[k][i], dp[k-1][j-1] + max_query(j,i));
}
}
}
return;
}
dp[1][0] = 0x3f3f3f3f;
for (int i = 1; i <= x; i++) {
dp[1][i] = max_query(1,i);
}
for (int k = 2; k <= p; k++) {
int size = std::max(2, std::min(k,BULAN));
std::vector<std::pair<uint32_t,int>> min(size,std::pair<uint32_t,int>(0x3f3f3f3f,0));
for (int i = 0; i < k; i++) {
dp[k][i] = 0x3f3f3f3f;
int pos = -1;
for (int j = 0; j < size; j++) {
if (min[j].first>dp[k-1][i]||(min[j].first==dp[k-1][i]&&min[j].second<i+1)) {
pos = j;
break;
}
}
if (pos!=-1) {
for (int j = size-1; j > pos; j--){
min[j] = min[j-1];
}
min[pos].first = dp[k-1][i];
min[pos].second = i+1;
}
}
for (int i = k; i <= x; i++) {
dp[k][i] = 0x3f3f3f3f;
for (int j = 0; j < size; j++) {
dp[k][i] = std::min(dp[k][i], min[j].first + max_query(min[j].second,i));
}
int pos = -1;
for (int j = 0; j < size; j++) {
if (min[j].first>dp[k-1][i]||(min[j].first==dp[k-1][i]&&min[j].second<i+1)) {
pos = j;
break;
}
}
if (pos!=-1) {
for (int j = size-1; j > pos; j--){
min[j] = min[j-1];
}
min[pos].first = dp[k-1][i];
min[pos].second = i+1;
}
}
}
}
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
std::cout.tie(NULL);
std::cin >> x >> p;
for (int i = 1; i <= x; i++) {
std::cin >> arr[i];
sp_tb[0][i] = arr[i];
}
build_sparse_table();
calculate_dp();
std::cout << dp[p][x] << "\n";
}
