#include <bits/stdc++.h>
#define ll long long
#define memaybeo main
#define en "\n";
#define hackspeed ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define dafug return 0;
#define fi first
#define se second
using namespace std;
const int mmb = 1e5 + 5,inf = 1e9+369;
int n,k,a[mmb],dp[mmb],lef[mmb];
pair<int,int>p[mmb];
signed main()
{
cin >> n >> k;
for(int i=1;i<=n;++i) cin >> a[i],lef[i] = max(lef[i-1],a[i]);
for(int j=2;j<=k;++j)
{
int sz = 0;
for(int i=1;i<=n;++i)
{
int ans = j <= i ? lef[i-1] : inf;
lef[i-1] = dp[i-1];
while(sz and a[i] >= p[sz-1].fi) ans = min(ans,p[--sz].se);
if(!sz or a[i] + ans < p[sz-1].fi + p[sz-1].se) p[sz++] = make_pair(a[i],ans);
dp[i] = p[sz-1].fi + p[sz-1].se;
}
lef[n] = dp[n];
}
cout << lef[n];
dafug
}
