#include <iostream>
#include <vector>
using namespace std;
using ll = long long;
using vll = vector<ll>;
#define sz(x) int(x.size())
const ll INF = 1'000'000'000'000'000LL;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int N, K;
cin >> N >> K;
vll A(1+N, INF);
for(int i = 1; i <= N; i++) cin >> A[i];
ll* DP[1+K];
DP[0] = new ll[1+N];
DP[1] = new ll[1+N];
for(int k = 2; k <= K; k++)
{
DP[k] = DP[k-2];
}
for(int i = 1; i <= N; i++)
{
DP[0][i] = DP[1][i] = +INF;
}
DP[0][0] = 0;
for(int k = 1; k <= K; k++)
{
// cerr << "\n\n\n\n\n k = " << k << '\n';
vector<ll> Aval;
vector<ll> DPprev;
vector<int> mxp;
vector<ll> mndp{INF};
// DP[k][0] = 0;
DP[k][0] = INF;
for(int i = 1; i <= N; i++)
{
// cerr << "\n\n\n";
// cerr << "i = " << i << '\n';
// cerr << "push value " << k-1 << ' ' << i-1 << " : " << DP[k-1][i-1] << '\n';
mxp.push_back(i-1);
// if(mndp.empty())
// mndp.push_back(DP[k-1][max(i-1, k-1)] + A[i]);
// else
// mndp.push_back(min(mndp.back(), DP[k-1][max(i-1, k-1)] + A[i]));
Aval.push_back(A[i]);
DPprev.push_back(DP[k-1][i-1]);
// mxp
mndp.push_back(min(mndp.back(), Aval.back() + DPprev.back()));
// cerr << "push P " << mndp.back() << '\n';
ll mnright = +INF;
while(A[mxp.back()] <= A[i])
{
mnright = min(mnright, DPprev.back());
mxp.pop_back();
mndp.pop_back();
Aval.pop_back();
DPprev.pop_back();
}
// cerr << "pop B " << mndp.back() << '\n';
// DPprev.back() = min()
Aval[sz(Aval)-1] = A[i];
DPprev[sz(DPprev)-1] = min(DPprev.back(), mnright);
// DPpre
mndp.pop_back();
mndp.push_back(min(mndp.back(), Aval.back() + DPprev.back()));
// cerr << "push Q " << mndp.back() << '\n';
DP[k][i] = mndp.back();
if(i < k) DP[k][i] = INF;
// cerr << k << ' ' << i << " : " << DP[k][i] << '\n';
}
}
cout << DP[K][N] << '\n';
}
