#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define fi first
#define se second
#define ll long long
using namespace std;
const int N = 1e5 + 7;
const int mod = 1e9 + 7;
int n,k;
int a[N];
int d[111][N];
void solve()
{
cin >> n >> k;
int mx = 0;
for( int i = 1; i <= n; i++ ){
cin >> a[i];
mx = max( mx , a[i] );
d[1][i] = mx;
}
for( int i = 2; i <= k; i++ ){
d[i][i] = d[i - 1][i - 1] + a[i];
stack < pair < int , int > > st;
st.push({d[i - 1][i - 1] , a[i]});
for( int j = i + 1; j <= n; j++ ){
int c = d[i - 1][j - 1];
while( !st.empty() && st.top().se <= a[j] ){
c = min( c , st.top().fi );
st.pop();
}
if( st.empty() || c + a[j] <= st.top().fi + st.top().se ){
st.push({c , a[j]});
}
d[i][j] = st.top().fi + st.top().se;
}
}
cout << d[k][n];
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
//freopen( "input.txt" , "r" , stdin );
//freopen( "output.txt" , "w" , stdout );
int t = 1;//cin >> t;
while( t-- ){
solve();
}
}
