#include<bits/stdc++.h>
#define fi first
#define se second
#define int long long
using namespace std;
using ll = long long;
using ii = pair<ll, ll>;
using aa = array<int,3>;
const int N = 1e6+5;
const int INF = 1e9;
int dp[100005][105];
int op[100005][105];
int a[100005];
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n,k;
cin >> n >> k;
for(int i=1;i<=n;i++) {
cin >> a[i];
dp[i][0]=1e18;
}
for(int j=1;j<=k;j++) {
stack<int> st;
dp[j-1][j]=1e18;
op[j-1][j]=dp[j-1][j-1];
for(int i=j;i<=n;i++) {
dp[i][j]=dp[i-1][j-1]+a[i];
op[i][j]=dp[i-1][j-1];
while(!st.empty() && a[i]>=a[st.top()]) {
if(dp[i][j]>op[st.top()][j]+a[i]) {
dp[i][j]=op[st.top()][j]+a[i];
op[i][j]=op[st.top()][j];
}
st.pop();
}
int pos;
if(st.empty()) {
if(dp[i][j]>op[j-1][j]+a[i]) {
dp[i][j]=op[j-1][j]+a[i];
op[i][j]=op[j-1][j];
}
}
else {
pos=st.top();
if(dp[i][j]>dp[pos][j]) {
dp[i][j]=dp[pos][j];
op[i][j]=1e18;
}
}
st.push(i);
}
}
cout << dp[n][k];
return 0;
}
