#include <iostream>
#include <vector>
#include <deque>
using namespace std;
const long long inf = 1e18;
int main() {
int n, k;
cin >> n >> k;
vector<int> a(n + 1);
for (int i = 1; i <= n; ++i) cin >> a[i];
vector<vector<long long>> dp(k + 1, vector<long long>(n + 1, inf));
dp[0][0] = 0;
for (int x = 1; x <= k; ++x) {
deque<int> dq;
vector<long long> mx(n + 1, 0);
for (int i = 1; i <= n; ++i) {
while (!dq.empty() && dq.front() < i - 1) dq.pop_front();
while (!dq.empty() && a[dq.back()] <= a[i]) dq.pop_back();
dq.push_back(i);
mx[i] = a[dq.front()];
}
deque<int> q;
q.push_back(0);
for (int i = 1; i <= n; ++i) {
while (!q.empty() && q.front() < i - 1) q.pop_front();
dp[x][i] = dp[x - 1][q.front()] + mx[i];
while (!q.empty() && dp[x - 1][q.back()] >= dp[x - 1][i]) q.pop_back();
q.push_back(i);
}
}
cout << dp[k][n] << endl;
return 0;
}
