/*
* @Author: RMQuan
* @Date: 2025-10-22 23:48:40
* @Last Modified by: RMQuan
* @Last Modified time: 2025-10-23 01:12:48
*/
/*idea :
*/
#include <bits/stdc++.h>
bool M1;
#define ll long long
#define INTMAX INT_MAX
#define INTMIN INT_MIN
#define LONGMAX LLONG_MAX
#define LONGMIN LLONG_MIN
#define fi first
#define se second
#define memfull(a,b) memset(a,b,sizeof(a));
#define endl '\n'
#define TASK "TEST"
#define file() if (fopen(TASK".inp","r")){freopen(TASK".inp","r",stdin); freopen(TASK".out","w",stdout);}
using namespace std;
const int MOD=1e9+7;
const int maxn=1e5+7;
const int inf=1e9;
int a[maxn],n,k;
int L[maxn],R[maxn];
struct ST
{
int N;
vector<int> st,lazy;
ST(int n):N(n),st(4*n+5,inf),lazy(4*n+5,inf){}
void fix(int id,int l,int r)
{
if (lazy[id]>=inf)return ;
st[id]=min(st[id],lazy[id]);
if (l!=r)
{
lazy[id*2]=min(lazy[id*2],lazy[id]);
lazy[id*2+1]=min(lazy[id*2+1],lazy[id]);
}
lazy[id]=inf;
}
void upd(int id,int l,int r,int u,int v,int val)
{
fix(id,l,r);
if (l>v||r<u)return ;
if (l>=u&&r<=v)
{
lazy[id]=min(lazy[id],val);
fix(id,l,r);
return ;
}
int mid=(l+r)/2;
upd(id*2,l,mid,u,v,val);
upd(id*2+1,mid+1,r,u,v,val);
st[id]=min(st[id*2],st[id*2+1]);
}
int get(int id,int l,int r,int u,int v)
{
fix(id,l,r);
if (l>v||r<u)return inf;
if (l>=u&&r<=v)return st[id];
int mid=(l+r)/2;
return min(get(id*2,l,mid,u,v),get(id*2+1,mid+1,r,u,v));
}
};
int32_t main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
file();
cin>>n>>k;
for (int i=1;i<=n;i++)cin>>a[i];
stack<int> st;
for (int i=1;i<=n;i++)
{
while (st.size()&&a[st.top()]<=a[i])st.pop();
if (st.size())L[i]=st.top()+1;
else L[i]=1;
st.push(i);
}
while (st.size())st.pop();
for (int i=n;i>=1;i--)
{
while(st.size()&&a[st.top()]<=a[i])st.pop();
if (st.size())R[i]=st.top()-1;
else R[i]=n;
st.push(i);
}
ST dp_prev(n);
ST dp_cur(n);
dp_prev.upd(1,0,n,0,0,0);
for (int j=1;j<=k;j++)
{
for (int i=1;i<=n;i++)
{
int l=max(L[i]-1,j-1);
int r=i-1;
if (l>r)continue;
int u=i;
int v=R[i];
int val=dp_prev.get(1,0,n,l,r);
dp_cur.upd(1,0,n,u,v,val+a[i]);
}
swap(dp_cur,dp_prev);
dp_cur=ST(n);
}
cout<<dp_prev.get(1,0,n,n,n);
bool M2;
cerr<<"-------------------------------------------------"<<endl;
cerr<<"Time : "<<clock()<<" ms"<<endl;
cerr<<"Memory : "<<abs(&M2-&M1)/1024/1024<<" MB"<<endl;
cerr<<"-------------------------------------------------"<<endl;
return 0;
}
