#include <bits/stdc++.h>
using namespace std;
int sir[100001] , minim[100001] , stiva[100001] , candidati[100001] , prefix[100001] , temporar[100001];
int main ()
{
ios :: sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
int lungime , secvente;
cin >> lungime >> secvente;
for (int indice = 1 ; indice <= lungime ; indice++)
{ cin >> sir[indice]; minim[indice] = max(minim[indice - 1] , sir[indice]); }
candidati[0] = prefix[0] = 1000000000;
for (int inceput = 2 ; inceput <= secvente ; inceput++)
{
for (int capat = inceput ; capat <= lungime ; capat++)
{
int __minim = minim[capat - 1];
while (stiva[0] && sir[stiva[stiva[0]]] <= sir[capat])
{ __minim = min(__minim , candidati[stiva[0]--]); }
stiva[++stiva[0]] = capat;
candidati[stiva[0]] = __minim;
prefix[stiva[0]] = min(prefix[stiva[0] - 1] , candidati[stiva[0]] + sir[capat]);
temporar[capat] = prefix[stiva[0]];
}
stiva[0] = 0;
for (int capat = inceput ; capat <= lungime ; capat++)
{ minim[capat] = temporar[capat]; }
}
cout << minim[lungime];
return 0;
}
