#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define pb push_back
#define all(a) a.begin(), a.end()
typedef long long ll;
typedef pair<int, int> ii;
const int N = 1e5 + 5;
const int mod = 1e9 + 7;
int n, k;
int a[N];
ll dp[105][N];
void solve()
{
cin >> n >> k;
for(int i = 1; i <= n; i++)
cin >> a[i];
for(int i = 0; i <= k; i++)
for(int j = 0; j <= n; j++)
dp[i][j] = 1e17;
dp[1][0] = 0;
for(int i = 1; i <= n; i++)
dp[1][i] = max(dp[1][i - 1], 1ll * a[i]);
for(int i = 2; i <= k; i++)
{
stack<pair<int, ll>> st;
for(int j = i; j <= n; j++)
{
ll prev = dp[i - 1][j - 1];
while(st.size() && a[j] >= a[st.top().F])
{
prev = min(prev, st.top().S);
st.pop();
}
int k = st.size() ? st.top().F : i - 1;
dp[i][j] = min(dp[i][k], prev + a[j]);
st.push({j, prev});
}
}
cout << dp[k][n];
}
signed main()
{
cin.tie(0)->sync_with_stdio(0);
int t = 1;
// cin >> t;
while(t--) solve();
return 0;
}
