# include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 2;
int n, a[N], k, dp[102][N];
int stk[N], pt, pf[N];
int main(){
cin >> n >> k;
for(int i = 1; i <= n; i ++)
cin >> a[i];
for(int i = 1; i <= n; i ++){
dp[1][i] = max(dp[1][i - 1], a[i]);
}
for(int i = 2; i <= k; i ++){
pt = 0;
deque < pair <int, int> > dq;
for(int j = i; j <= n; j ++){
while(pt > 0 && a[ stk[pt] ] < a[j])
pt --;
stk[++ pt] = j;
while(!dq.empty() && dq.back().first > dp[i - 1][j - 1])
dq.pop_back();
dq.push_back({dp[i - 1][j - 1], j - 1});
int lo = 0, hi = (int)dq.size() - 1;
while(lo <= hi){
int md = (lo + hi) >> 1;
if(dq[md].second >= max(stk[pt - 1], i - 1))
hi = md - 1;
else
lo = md + 1;
}
pf[pt] = dq[hi + 1].first + a[j];
if(pt > 1)
pf[pt] = min(pf[pt - 1], pf[pt]);
dp[i][j] = pf[pt];
}
}
cout << dp[k][n] << endl;
}
