//#pragma GCC optimize("O3")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,tune=native")
//#pragma GCC optimize ("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e5 + 5;
const int K = 105;
int dp[K][N];
int a[N];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int n, k;
cin >> n >> k;
for (int i = 1; i <= n; i++) {
cin >> a[i];
dp[1][i] = max(dp[1][i - 1], a[i]);
}
for (int i = 2; i <= k; i++) {
vector<pair<int, int>> kek;
for (int j = 1; j <= n; j++) {
int cur = dp[i - 1][j - 1];
if (!cur) {
cur = 1e9;
}
while (!kek.empty() && kek.back().first < a[j]) {
cur = min(cur, kek.back().second);
kek.pop_back();
}
if (kek.empty() || a[j] + cur < kek.back().first + kek.back().second) {
kek.emplace_back(a[j], cur);
}
dp[i][j] = kek.back().first + kek.back().second;
}
}
cout << dp[k][n];
return 0;
}
