#include <bits/stdc++.h>
using namespace std;
#define int long long
const int INF = 5e18;
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(nullptr); cout.tie(nullptr);
int N, K;
cin >> N >> K;
vector<int> a(N + 1, 0);
vector<vector<int>> dp(N + 1, vector<int> (K + 1, INF));
for(int i = 1; i <= N; ++i) cin >> a[i];
for(int i = 0; i <= N; ++i) dp[i][0] = 0;
// 6 1 2 3 4 5, K = 3
for(int i = 1, mx = 1; i <= N; ++i){
mx = max(mx, a[i]);
dp[i][1] = mx;
}
for(int k = 2; k <= K; ++k){
stack<int> st;
vector<int> mn(N + 1, INF);
for(int i = 1; i <= N; ++i){
while(st.size() && a[st.top()] <= a[i]){
dp[i][k] = min(dp[i][k], dp[st.top() - 1][k - 1] + a[i]);
mn[i] = min(dp[st.top()][k - 1], mn[st.top()]);
dp[i][k] = min(dp[i][k], mn[i] + a[i]);
st.pop();
}
if(st.size()){
dp[i][k] = min(dp[i][k], dp[st.top()][k]); // extend
dp[i][k] = min(dp[i][k], dp[st.top()][k - 1] + a[i]); // from st.top() + 1, to i
dp[i][k] = min(dp[i][k], dp[st.top() - 1][k - 1] + a[st.top()]);
dp[i][k] = min(dp[i][k], mn[st.top()] + a[i]);
}
dp[i][k] = min(dp[i][k], dp[i - 1][k - 1] + a[i]);
st.push(i);
}
}
cout << dp[N][K] << "\n";
return 0;
}
