#include <bits/stdc++.h>
#define endl '\n'
#include<stack>
using namespace std;
stack<long long>st;
long long a[10000000], pr[10000000], dp[1000000][100];
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
long long n,i,j,k;
cin>>n>>k;
for(i=1; i<=n; i++)
{
cin>>a[i];
while(!st.empty() && a[st.top()]<=a[i])st.pop();
if(!st.empty())pr[i]=st.top();
st.push(i);
}
for(j=1;j<=n;j++)dp[j][1]=max(a[j], dp[j-1][1]);
for(i=1;i<=n;i++)
{
for(j=2;j<=k;j++)
{
int p=0;
if(pr[i]==0){pr[i]=j-1;p=1;}
if(dp[pr[i]][j]!=(long long)(0) && !p) dp[i][j]=min(dp[pr[i]][j-1]+a[i], dp[pr[i]][j]);
else dp[i][j]=dp[pr[i]][j-1]+a[i];
if(p)pr[i]=0;
}
}
cout<<dp[n][k]<<endl;
}
