#include <bits/stdc++.h>
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define ll long long
using namespace std;
const ll N=105,INF=1e9;
ll a[N],b[N],suf[N],y,z,x,n,q,mx,mn,k,ans,ind;
ll dp[N][N];
bool ok,okk;
stack <ll> st;
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cin >> n >> q;
for (int i=1; i<=n; i++) cin >> a[i];
for (int i=0; i<=n; i++){
for (int k=1; k<=n; k++){
dp[i][k]=INF;
}
}
mx=a[1];
for (int i=1; i<=n; i++) dp[i][1]=mx,mx=max(mx,a[i+1]); mx=0;
for (int i=1; i<=q; i++){
mx+=a[i];
dp[i][i]=mx;
}
mx=0;
for (int i=0; i<=q; i++) dp[0][i]=0;
for (int k=2; k<=q; k++){
while (st.size()>0) st.pop();
for (int i=k; i<=n; i++){
mn=dp[i-1][k-1];
while (st.size()>0 && a[i]>a[st.top()]){
mn=min(mn,dp[st.top()][k]-a[st.top()]); st.pop();
}
if (st.size()>0)
dp[i][k]=min(dp[i][k],dp[st.top()][k]);
dp[i][k]=min(dp[i][k],mn+a[i]);
st.push(i);
}
}
cout<<dp[n][q]<<endl;
}
