#include <bits/stdc++.h>
using namespace std;
//#define ll long long//#define fi first//#define se second
#define ll long long
#define memaybeo main
#define en "\n";
#define hackspeed ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define dafug return 0;
const int mmb = 1e5+2;
int n,k,a[mmb],lef[mmb];
ll seg[4*mmb],dp[mmb][102];
void update(int x,int l,int r,int i,int vl)
{
if (l == r) { seg[x] = vl; return; }
int m = (l+r)/2;
if (i <= m) update(2*x,l,m,i,vl);
else update(2*x+1,m+1,r,i,vl);
seg[x] = min(seg[2*x],seg[2*x+1]);
}
ll MIN(int x,int l,int r,int i,int j)
{
if (j < l || i > r) return 1e18;
if (i <= l && j >= r) return seg[x];
int m = (l+r)/2;
return min(MIN(2*x,l,m,i,j) , MIN(2*x+1,m+1,r,i,j));
}
void dopdop()
{
cin >> n >> k;fill(dp[0],dp[0]+k+1,(ll)1e18);
for(int i=1;i<=n;++i) cin >> a[i] , fill(dp[i],dp[i]+k+1,(ll)1e18);
dp[1][1] = a[1];
for(int i=2;i<=n;++i) dp[i][1] = max((ll)a[i],dp[i-1][1]);
///////////////
stack<int> st;
for(int i=n;i>0;--i)
{
while(!st.empty() && a[i] > a[st.top()]) lef[st.top()] = i , st.pop();
st.push(i);
}
while(!st.empty()) lef[st.top()] = 0 , st.pop();
//cout << en;for(int i=1;i<=n;++i) cout << lef[i] << ' ';cout << en;
//////////////
for(int j=2;j<=k;++j)
{
fill(seg,seg+4*mmb,(ll)1e18);
for(int i=1;i<j;++i) update(1,1,n,i,dp[i][j-1]);// , cout << dp[i][j-1] << en;
//cout << MIN(1,1,n,1,1) << en;
for(int i=j;i<=n;++i)
{
int lim = max(lef[i],j-1);
dp[i][j] = min(MIN(1,1,n,lim,i-1) + (ll)a[i] , dp[lef[i]][k]);
//cout << MIN(1,1,n,lim,i-1) << ' ' << lim << ' ' << i-1 << en;
update(1,1,n,i,dp[i][j-1]);
}
}
/*cout << en;
for(int i=1;i<=n;++i)
{
for(int j=1;j<=k;++j) cout << dp[i][j] << ' ';cout << en;
}*/
cout << dp[n][k];
}
signed memaybeo()
{
hackspeed
//skibidi();
dopdop();
//yesyes();
dafug
}
