// Born_To_Laugh - Hughie Do
#include <bits/stdc++.h>
#define alle(AC) AC.begin(), AC.end()
#define fi first
#define se second
using namespace std;
typedef long long ll;
[[maybe_unused]] const ll MOD = 998244353, INF = 3e18 + 7;
const int maxn = 1e5 + 10;
int n, k;
ll a[maxn], prefm[maxn];
ll dp[maxn][110];
void solve(){
cin >> n >> k;
for(int i=0; i<=n; ++i)
for(int j=0; j<=k; ++j) dp[i][j] = INF;
dp[0][0] = 0;
for(int i=1; i<=n; ++i){
cin >> a[i];
prefm[i] = max(prefm[i - 1], a[i]);
dp[i][1] = prefm[i];
}
for(int j=2; j<=k; ++j){
multiset<ll> num;
vector<int> st;
vector<ll> mindp(n + 1, INF);
mindp[j - 1] = dp[j - 1][j - 1];
for(int i=j; i<=n; ++i){
mindp[i] = dp[i][j - 1];
ll miner = INF;
while(!st.empty() && a[st.back()] <= a[i]){
int id = st.back();
miner = min(miner, mindp[id]);
st.pop_back();
int pid = (st.empty() ? j - 1 : st.back());
num.erase(num.lower_bound(mindp[pid] + a[id]));
}
int pid = (st.empty() ? j - 1 : st.back());
mindp[pid] = min(mindp[pid], miner);
int id = i;
st.push_back(id);
num.insert(mindp[pid] + a[id]);
dp[i][j] = *num.begin();
// cout << i << ' ' << j << ' ' << dp[i][j] << '\n';
// for(auto &elm: num) cout << elm << '\n';
}
}
cout << dp[n][k] << '\n';
}
signed main(){
// freopen("inp.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
solve();
}
