#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define ll long long
#define ld long double
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define SZ(x) (int)(x).size()
template <typename T> using ord_set = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int n0 = 100003, k0 = 101;
int n, k, a[n0], dp[2][n0];
struct T {
int x, y, mn;
void merge(const T & t) {
if (t.x <= x) x = t.x;
mn = min(mn, x + y);
}
};
stack <T> st;
int main() {
ios_base::sync_with_stdio(false), cin.tie(NULL);
#ifdef LOCAL
freopen("input.txt", "r", stdin);
#endif
cin >> n >> k;
for (int i = 1; i <= n; i++) {
cin >> a[i];
dp[1][i] = max(dp[1][i - 1], a[i]);
}
T cur;
for (int i = 2; i <= k; i++) {
while (!st.empty()) st.pop();
for (int j = i; j <= n; j++) {
cur.x = dp[(i & 1) ^ 1][j - 1], cur.y = a[j];
cur.mn = cur.x + cur.y;
while (!st.empty() && st.top().y <= cur.y) {
cur.merge(st.top());
st.pop();
}
if (!st.empty()) {
cur.mn = min(cur.mn, st.top().mn);
}
st.push(cur);
dp[i & 1][j] = cur.mn;
}
}
cout << dp[k & 1][n];
}
