#pragma GCC optimize("O2")
#include<bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define multiTest unsigned long long numTest; for (cin >> numTest; numTest--;)
#define db(val) "[" #val " = " << (val) << "] "
#define el cout << '\n'
#define taskName "kblocks"
using namespace std;
typedef long long ll;
typedef pair <ll, ll> ii;
const ll si = 1e5 + 9;
const ll mod = 1e9 + 7;
int n, k, dp[109][si], a[si], lr[si], mn[si];
/*
testing someone's solution
*/
inline void solve()
{
cin >> n >> k;
for (int i = 1; i <= n; ++i) cin >> a[i];
memset(dp, 0x3f, sizeof(dp));
dp[1][0] = 0;
for (int i = 1; i <= n; ++i) dp[1][i] = max(dp[1][i - 1], a[i]);
for (int i = 1; i <= n; ++i) for (lr[i] = i - 1; lr[i] && a[lr[i]] <= a[i]; ) lr[i] = lr[lr[i]];
for (int i = 2; i <= k; ++i)
{
mn[i - 1] = 1e9;
for (int j = i; j <= n; ++j)
{
mn[j] = dp[i - 1][j - 1];
for (int t = j - 1; t > lr[j]; t = lr[t]) mn[j] = min(mn[j], mn[t]);
dp[i][j] = min(dp[i][lr[j]], mn[j] + a[j]);
}
}
cout << dp[k][n], el;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
// multiTest
{
solve();
el;
}
}
