#include <bits/stdc++.h>
using namespace std;
const int nx=1e5+5, kx=105, lx=17;
int n, k, v[nx], dp[kx][nx], mx;
void solve(int l, int r, int ly, int optl, int optr)
{
if (r<l) return;
int md=(l+r)/2;
//cout<<ly<<' '<<l<<' '<<md<<' '<<r<<' '<<optl<<' '<<optr<<'\n';
pair<int, int> p={1e9, -1};
mx=0;
for (int i=md; i>optr; i--) mx=max(mx, v[i]);
for (int i=min(optr, md); i>=optl; i--) mx=max(mx, v[i]), p=min(p, {mx+dp[ly-1][i-1], i});
dp[ly][md]=p.first;
solve(l, md-1, ly, optl, p.second);
solve(md+1, r, ly, p.second, optr);
}
int main()
{
cin.tie(NULL)->sync_with_stdio(false);
cin>>n>>k;
for (int i=1; i<=n; i++) cin>>v[i], dp[0][i]=1e9;
for (int i=1; i<=k; i++) dp[i][0]=1e9, solve(1, n, i, 1, n);
//for (int i=1; i<=k; i++) for (int j=1; j<=n; j++) cout<<i<<' '<<j<<' '<<dp[i][j]<<'\n';
cout<<dp[k][n];
}
