# include <bits/stdc++.h>
# define speed ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
# define int long long
# define fi first
# define se second
using namespace std;
const int N = 1e5 + 7;
const int mod = 1e9 + 7;
int a[N], dp[105][N];
int32_t main() {
speed;
int n, k;
cin >> n >> k;
for ( int i = 1; i <= n; i++ ) {
cin >> a[i];
}
for ( int i = 1; i <= n; i++ ) {
dp[0][i] = 1e9;
}
stack < pair < int, int > > st;
for ( int i = 1; i <= k; i++ ) {
while ( !st.empty() ) {
st.pop();
}
dp[i][i] = dp[i - 1][i - 1] + a[i];
st.push( { a[i], dp[i - 1][i - 1] } );
for ( int j = i + 1; j <= n; j++ ) {
int x = dp[i - 1][j - 1];
while ( !st.empty() && st.top().fi <= a[j] ) {
x = min( x, st.top().se );
st.pop();
}
if ( st.empty() || st.top().fi + st.top().se > a[j] + x ) {
st.push( { a[j ], x } );
}
dp[i][j] = st.top().fi + st.top().se;
}
}
cout << dp[k][n];
}
