#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N=1e5+5;
const int K=105;
const ll oo=(long double)1e18+1;
int n,k;
int a[N];
namespace sub4
{
const int oo=1e9+1;
int ma,u,v,x;
int dp[N],t[4*N],lazy[4*N];
stack <int> st;
void build(int id,int l,int r)
{
lazy[id]=0;
if (l==r)
{
t[id]=dp[l-1];
return;
}
int m=(l+r)/2;
build(id*2,l,m);
build(id*2+1,m+1,r);
t[id]=min(t[id*2],t[id*2+1]);
}
void down(int id)
{
if (lazy[id])
{
lazy[id*2]+=lazy[id];
lazy[id*2+1]+=lazy[id];
t[id*2]+=lazy[id];
t[id*2+1]+=lazy[id];
lazy[id]=0;
}
}
void update(int id,int l,int r)
{
if (u>r or v<l) return;
if (u<=l and v>=r)
{
t[id]+=x;
lazy[id]+=x;
return;
}
down(id);
int m=(l+r)/2;
update(id*2,l,m);
update(id*2+1,m+1,r);
t[id]=min(t[id*2],t[id*2+1]);
}
int get(int id,int l,int r)
{
if (u>r or v<l) return oo;
if (u<=l and v>=r) return t[id];
down(id);
int m=(l+r)/2;
return min(get(id*2,l,m),get(id*2+1,m+1,r));
}
void solve()
{
ma=0;
for (int i=1;i<=n;i++)
{
ma=max(ma,a[i]);
dp[i]=ma;
}
for (int rep=2;rep<=k;rep++)
{
build(1,1,n);
while (!st.empty()) st.pop();
a[rep-1]=oo;
st.push(rep-1);
for (int i=rep;i<=n;i++)
{
u=st.top()+1;
while (!st.empty() and a[st.top()]<a[i])
{
v=st.top();
st.pop();
u=st.top()+1;
x=-a[v];
update(1,1,n);
}
v=i;
x=a[i];
update(1,1,n);
st.push(i);
u=rep;
v=i;
dp[i]=get(1,1,n);
}
}
cout << dp[n];
}
}
int main()
{
ios_base::sync_with_stdio(NULL);
cin.tie(NULL); cout.tie(NULL);
cin >> n >> k;
for (int i=1;i<=n;i++)
cin >> a[i];
sub4::solve();
}
