/*
* @Author: RMQuan
* @Date: 2025-10-22 23:48:40
* @Last Modified by: RMQuan
* @Last Modified time: 2025-10-23 01:57:18
*/
/*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 LOG=16;
const int inf=1e9;
int a[maxn],n,k;
int rmq[maxn][LOG+1];
struct query
{
int pos,val,type;
};
bool cmp(const query &x,const query &y)
{
if (x.pos!=y.pos)return x.pos<y.pos;
return x.type<y.type;
}
void build(const vector<pair<int,pair<int,int>>> &qr)
{
for (int i=0;i<=n;i++) rmq[i][0]=inf;
vector<query> vt;
vector<int> vals;
for (auto &i: qr){
vt.push_back({i.se.fi, i.fi, 1});
vt.push_back({i.se.se+1, i.fi, -1});
vals.push_back(i.fi);
}
for (int i=0;i<=n;i++) vt.push_back({i,0,2});
sort(vt.begin(), vt.end(), cmp);
// nén giá trị
sort(vals.begin(), vals.end());
vals.erase(unique(vals.begin(), vals.end()), vals.end());
int m = vals.size();
auto id = [&](int x){ return (int)(lower_bound(vals.begin(), vals.end(), x) - vals.begin()) + 1; };
vector<int> bit(m+5, 0);
auto add=[&](int i,int v){
for (;i<=m;i+=i&-i) bit[i]+=v;
};
auto sum=[&](int i){
int s=0;
for (;i>0;i-=i&-i) s+=bit[i];
return s;
};
auto find_first=[&](){
if (sum(m)==0) return inf;
int pos=0;
for (int pw=(1<<20);pw;pw>>=1){
if (pos+pw<=m && bit[pos+pw]==0){
pos+=pw;
}else if (pos+pw<=m && bit[pos+pw]<0){
pos+=pw;
}
}
// find first with prefix sum >=1
int l=1,r=m,res=m;
while(l<=r){
int mid=(l+r)/2;
if (sum(mid)>=1) res=mid,r=mid-1;
else l=mid+1;
}
return vals[res-1];
};
for (auto &q: vt){
if (q.type==1){
add(id(q.val),1);
}
else if (q.type==-1){
add(id(q.val),-1);
}
else{
rmq[q.pos][0]=find_first();
}
}
for (int j=1;j<=LOG;j++)
for (int i=0;i+(1<<j)-1<=n;i++)
rmq[i][j]=min(rmq[i][j-1], rmq[i+(1<<(j-1))][j-1]);
}
int get(int l,int r)
{
int k=__lg(r-l+1);
return min(rmq[l][k],rmq[r-(1<<k)+1][k]);
}
int L[maxn],R[maxn];
int dp[maxn];
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);
}
vector<pair<int,pair<int,int> > >qr;
qr.push_back({0,{0,0}});
build(qr);
for (int j=1;j<=k;j++)
{
qr.clear();
for (int i=1;i<=n;i++)
{
int l=L[i]-1;
int r=i-1;
int u=i;
int v=R[i];
int val=get(l,r);
qr.push_back({val+a[i],{u,v}});
cerr<<val+a[i]<<" "<<u<<" "<<v<<endl;
}
build(qr);
}
cout<<get(n,n);
bool M2;
cerr<<"-------------------------------------------------"<<endl;
cerr<<"Time : "<<clock()<<" ms"<<endl;
cerr<<"Memory : "<<abs(&M2-&M1)/1024/1024<<" MB"<<endl;
cerr<<"-------------------------------------------------"<<endl;
return 0;
}
