//Problem link: https://oj.uz/problem/view/IZhO14_blocks
// Libraries
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> indexed_set; //find_by_order, order_of_key
#include <ext/rope>
using namespace __gnu_cxx;
// Data types
typedef string str;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ld, ld> pld;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef unsigned int ui;
typedef unsigned long long ull;
// Methods
#define MP make_pair
#define F first
#define S second
#define PB push_back
#define sz(a) (int)(a).size()
// Iterator
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
// Variable names
#define y1 y1___
// Loops
#define FOR(i,a,b) for (int i = (a); i <= (b); ++i)
#define RFOR(i,a,b) for (int i = (a); i >= (b); --i)
// Constant variables
const int MOD = 1000000007; // 998244353
const int INF = 1000000005;
const ll LLINF = 1000000000000000005LL;
const ld PI = acos((ld)-1);
const ld EPS = 1e-9;
void setIO(str name="") {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout << setprecision(15) << fixed;
if (fopen((name + ".INP").c_str(), "r")) {
freopen((name + ".INP").c_str(), "r", stdin);
freopen((name + ".OUT").c_str(), "w", stdout);
}
}
inline ll pw(ll bs, ll p, int mod=MOD) {
ll res = 1;
ll tmp = bs;
while (p) {
if (p & 1) {
res = res*tmp%mod;
}
tmp = tmp*tmp%mod;
p >>= 1;
}
return res;
}
inline ll inv(ll x, int mod=MOD) {
return pw(x, mod-2, mod);
}
mt19937_64 rd(chrono::steady_clock::now().time_since_epoch().count());
ll rnd(ll l, ll r) {
return l + (ll)(rd() % (ull)(r-l+1));
}
int test = 1;
const int MAXN = 100005;
const int MAXK = 105;
int n, k;
int a[MAXN];
int dp[2][MAXN];
stack<pii> st;
void solve() {
cin >> n >> k;
FOR(i, 1, n) {
cin >> a[i];
}
dp[0][0] = 0;
FOR(i, 1, n) dp[0][i] = INF;
FOR(_, 1, k) {
dp[1][0] = INF;
FOR(i, 1, n) {
int minF = dp[0][i-1];
dp[1][i] = minF + a[i];
while (!st.empty() && a[st.top().F] < a[i]) {
minF = min(minF, st.top().S);
dp[1][i] = minF + a[i];
st.pop();
}
if (!st.empty()) {
dp[1][i] = min(dp[1][i], dp[1][st.top().F]);
}
st.push(MP(i, minF));
}
FOR(i, 0, n) {
dp[0][i] = dp[1][i];
}
while (!st.empty()) st.pop();
}
cout << dp[0][n] << '\n';
}
int main() {
setIO();
//cin >> test;
FOR(_, 1, test) {
solve();
}
return 0;
}
