#include<bits/stdc++.h>
#define maxn 100005
using namespace std;
int n, k, a[maxn], F[maxn][105];
int main()
{
//freopen("BLOCKS.inp","r",stdin);
//freopen("BLOCKS.out","w",stdout);
cin >> n >> k;
for(int i=1;i<=n;i++)
{
cin >> a[i];
}
for(int i=0;i<=n;i++)
{
for(int j=0;j<=k;j++) F[i][j] = 1e9+9;
}
F[0][1] = 0;
for(int i=1;i<=n;i++) F[i][1] = max(F[i-1][1], a[i]);
for(int i=2;i<=k;i++)
{
stack< pair<int,int> > P;
for(int j=i;j<=n;j++)
{
int cur = F[j-1][i-1];
while(P.size() && a[P.top().second] <= a[j])
{
cur = min(cur, P.top().first);
P.pop();
}
F[j][i] = min(cur + a[j], F[P.empty() ? 0 : P.top().second][i]);
P.push( make_pair(cur, i));
}
}
cout << F[n][k];
}
