#include <bits/stdc++.h>
using namespace std;
#define minim(X, Y) (X = min(X, Y))
const int INF = 2e9;
int main() {
ios::sync_with_stdio(0), cin.tie(0);
int N, K;
cin >> N >> K;
int A[N+1] {INF};
for(int i = 1; i <= N; ++i)
cin >> A[i];
int dp[N+1][K+1], dpMin[N+1][K+1];
fill(dp[0], dp[0] + K + 1, INF);
fill(dpMin[0], dpMin[0] + K + 1, INF);
dp[0][0] = 0;
vector<int> s {0};
for(int i = 1; i <= N; ++i) {
copy(dp[i-1], dp[i-1] + K + 1, dpMin[i]);
while(A[s.back()] <= A[i]) {
int j = s.back();
s.pop_back();
for(int k = 0; k <= K; ++k)
minim(dpMin[i][k], dpMin[j][k]);
}
copy(dp[s.back()], dp[s.back()] + K + 1, dp[i]);
dp[i][0] = INF;
for(int k = 1; k <= K; ++k)
minim(dp[i][k], A[i] + dpMin[i][k - 1]);
s.push_back(i);
}
cout << dp[N][K];
}
