// 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];
vector<vector<int>> spt;
int qr(int l, int r){
int lg = log2(r - l + 1);
return min(spt[l][lg], spt[r - (1 << lg) + 1][lg]);
}
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;
spt.assign(n + 1, vector<int> (20, 0));
for(int i=1; i<=n; ++i) spt[i][0] = dp[i][j - 1];
for(int b=1; b<20; ++b){
for(int i=1; i<=n; ++i){
if(i + (1 << b) - 1 > n) break;
spt[i][b] = min(spt[i][b - 1], spt[i + (1 << (b - 1))][b - 1]);
}
}
for(int i=j; i<=n; ++i){
while(!st.empty() && a[st.back()] <= a[i]){
int id = st.back();
st.pop_back();
int pid = (st.empty() ? j - 1 : st.back());
num.erase(num.lower_bound(qr(pid, id - 1) + a[id]));
}
int pid = (st.empty() ? j - 1 : st.back());
int id = i;
st.push_back(id);
num.insert(qr(pid, id - 1) + 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();
}
