#include<bits/stdc++.h> #define pii pair<int,int> #define ll long long using namespace std; const int inf=1e9; int main() { int n,k; cin>>n>>k; int a[n+1]; for(int i=1;i<=n;i++)cin>>a[i]; int dp[n+1][k+1]; dp[1][1]=a[1]; int mx[n+1][k+1]; mx[1][1]=a[1]; for(int i=2;i<=k;i++)dp[1][i]=inf,mx[1][i]=0; for(int i=2;i<=n;i++) { dp[i][1]=max(dp[i-1][1],a[i]); mx[i][1]=dp[i][1]; for(int j=2;j<=k;j++) { int v1=dp[i-1][j-1]+a[i]; int v2=dp[i-1][j]-mx[i-1][j]+max(mx[i-1][j],a[i]); if(v1<v2) { dp[i][j]=v1; mx[i][j]=a[i]; } else { dp[i][j]=v2; mx[i][j]=max(mx[i-1][j],a[i]); } } } cout<<dp[n][k]<<endl; return 0; }