#include<bits/stdc++.h>
#define IOS ios_base::sync_with_stdio(false);cin.tie();cout.tie();
#define all(x) x.begin(), x.end()
#define int long long
#define pq priority_queue
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound
#define pb push_back
#define pp pop_back
#define F first
#define S second
using namespace std;
int n, k, mx;
int a[100001];
int dp[100001][101];
stack<pair<int, int>> st;
void solve () {
cin >> n >> k;
for (int i = 1; i <= n; i++) {
cin >> a[i];
mx = max(mx, a[i]);
dp[i][1] = mx;
}
for (int i = 2; i <= k; i++) {
while (!st.empty()) st.pop();
for (int j = 1; j <= n; j++) {
if (j < i) {dp[j][i] = 1e9; continue ;}
int mn = dp[j-1][i-1];
while (!st.empty() && a[st.top().F] <= a[n]) {mn = min(mn, st.top().S); st.pop();}
dp[j][i] = mn + a[j];
if (!st.empty()) dp[j][i] = min(dp[j][i], dp[st.top().F][i]);
st.push({j, mn});
}
}
cout << dp[n][k];
}
signed main() {IOS solve(); return 0;}
