#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N=1e5+5;
int n,k;
ll a[N],dp[2][N];
struct Info{
ll mx,opt,mn;
};
int main() {
cin >> n >> k;
for(int i=1;i<=n;i++){
cin >> a[i];
}
for(int i=1;i<=n;i++){
dp[1][i]=max(dp[1][i-1],a[i]);
}
for(int s=2;s<=k;s++){
int cur=s%2,pre=1-cur;
vector<Info> st;
for(int i=s;i<=n;i++){
Info res{a[i],dp[pre][i-1]+a[i],0LL};
while(!st.empty()&&st.back().mx<=a[i]){
Info tmp=st.back();
st.pop_back();
ll diff=a[i]-tmp.mx;
res.opt=min(res.opt,tmp.opt+diff);
}
res.mn=res.opt;
if(!st.empty()){
res.mn=min(res.mn,st.back().mn);
}
st.push_back(res);
dp[cur][i]=res.mn;
}
}
cout << dp[k%2][n] << "\n";
}
