#include <bits/stdc++.h>
using namespace std;
#define Task "main"
#define ll long long
#define pb push_back
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define FOD(i, a, b) for (int i = (a); i >= (b); i--)
#define TIME (1.0 * clock() / CLOCKS_PER_SEC)
#define F first
#define S second
const int N = 1e5 + 5;
const int INF = 1e9;
const int MOD = 1e9 + 7;
template<class X, class Y>
bool minimize(X &x, Y y) {
if (x > y) {
x = y;
return true;
} else return false;
}
template<class X, class Y>
bool maximize(X &x, Y y) {
if (x < y) {
x = y;
return true;
} else return false;
}
int n, k;
int a[N];
namespace sub3 {
const int N = 1e2 + 5;
int dp[N][N];
void solve() {
memset(dp, 0x3f, sizeof(dp));
dp[0][0] = 0;
FOR(group, 1, k) FOR(i, group, n) {
int maxx = a[i];
FOD(j, i, 1) {
maximize(maxx, a[j]);
minimize(dp[group][i], dp[group - 1][j - 1] + maxx);
}
}
cout << dp[k][n] << "\n";
}
}
namespace subFull {
int dp[105][N];
void solve() {
memset(dp, 0x3f, sizeof(dp));
dp[0][0] = 0;
a[0] = INF;
FOR(group, 1, k) {
stack<pair<int, int>> st;
st.push({INF, INF});
FOR(i, group, n) {
int curDP = dp[group - 1][i - 1];
while (!st.empty() && st.top().F <= a[i]) {
minimize(curDP, st.top().S);
st.pop();
}
if (st.top().F + st.top().S > a[i] + curDP) {
st.push({a[i], curDP});
}
dp[group][i] = st.top().F + st.top().S;
}
}
cout << dp[k][n] << "\n";
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
if (fopen(Task".INP", "r")) {
freopen(Task".INP", "r", stdin);
freopen(Task".OUT", "w", stdout);
}
cin >> n >> k;
FOR(i, 1, n) cin >> a[i];
if (n <= 100) sub3::solve();
else subFull::solve();
cerr << TIME << "s\n";
return 0;
}
