#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;
const int N = 100'032;
const int K = 110;
const ll inf = 1e15;
ll dp[K][N];
ll a[N];
int n;
ll seg[K][2*N];
ll get(int k, int l, int r)
{
l += N; r += N;
ll ans = inf;
while (l < r) {
if (l&1) ans = min(ans, seg[k][l++]);
if (r&1) ans = min(ans, seg[k][--r]);
l /= 2; r /= 2;
}
return ans;
}
void up(int k, int i, ll x)
{
i += N;
while (i) {
seg[k][i] = min(seg[k][i], x);
i /= 2;
}
}
int main()
{
cin.tie(0) -> sync_with_stdio(false);
int k;
cin >> n >> k;
Loop (i,0,n)
cin >> a[i];
memset(seg, 32 /* inf */, sizeof(seg));
dp[1][0] = a[0];
up(1, 0, dp[1][0]);
Loop (i,2,k+1)
dp[i][0] = inf;
vector<int> vec;
vec.push_back(0);
Loop (i,1,n) {
while (vec.size() && a[vec.back()] < a[i])
vec.pop_back();
dp[1][i] = max(a[i], dp[1][i-1]);
up(1, i, dp[1][i]);
Loop (j,2,k+1) {
dp[j][i] = get(j-1, vec.size()?
vec.back():
0, i) + a[i];
if (vec.size()) {
dp[j][i] = min(dp[j][i],
dp[j][vec.back()]);
}
up(j, i, dp[j][i]);
}
vec.push_back(i);
}
cout << dp[k][n-1] << '\n';
}
