#include <bits/stdc++.h>
#define SPED \
ios_base::sync_with_stdio(false); \
cin.tie(0); \
cout.tie(0);
#define endl "\n"
#define fi first
#define se second
#define lint long long
#define fami signed
#define lore main
#define freefire freopen
const lint INF = 1e15;
using namespace std;
int n, k;
lint a[100005], dp[105][100005];
fami lore()
{
SPED;
cin >> n >> k;
for (int i = 1; i <= n; i++)
cin >> a[i];
for (int i = 1; i <= n; i++)
dp[1][i] = max(dp[1][i - 1], a[i]);
for (int i = 2; i <= k; i++)
{
vector<pair<lint, int>> st;
for (int j = 1; j <= n; j++)
{
lint cur = dp[i - 1][j - 1];
while (!st.empty() and a[st.back().se] <= a[j])
{
cur = min(cur, st.back().fi);
st.pop_back();
}
lint temp = st.empty() ? INF : dp[i][st.back().se];
dp[i][j] = min(cur + a[j], temp);
st.emplace_back(cur, j);
}
st.clear();
}
cout << dp[k][n];
}
// Let your soul wander where dreams are born.
