#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
using namespace std;
int n,k;
long long a[1000005];
long long dp[2][1000005];
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> k;
for(int i = 1;i <= n;i++){
cin >> a[i];
}
dp[0][0] = 0;
dp[0][1] = a[1];
for (int i = 2; i <= n; i++){
dp[0][i] = max(dp[0][i-1], 1LL * a[i]);
}
for (int j = 2; j <= k; j++){
for (int i = j; i <= n; i++){
dp[1][i] = LLONG_MAX;
}
deque<int> st;
for (int i = j; i <= n; i++){
dp[1][i] = dp[0][i-1] + a[i];
while (!st.empty() && a[st.back()] <= a[i]){
int j = st.back();
st.pop_back();
dp[1][i] = min(dp[1][i], dp[1][j] - a[j] + a[i]);
}
if (!st.empty()){
dp[1][i] = min(dp[1][i], dp[1][st.front()]);
}
st.push_back(i);
}
for(int i = 1;i <= n;i++) dp[0][i] = dp[1][i];
}
cout << dp[0][n] << "\n";
return 0;
}
