#include <iostream>
#include <stack>
#include <cstring>
#include <vector>
#include <algorithm>
#include <deque>
#include <set>
#include <utility>
#include <array>
using i64 = long long;
using u64 = unsigned long long;
using f64 = double;
using f80 = long double;
using namespace std;
#define ALL(x) x.begin(), x.end()
#define ShinLena cin.tie(nullptr)->sync_with_stdio(false);
#define N 100000
template <typename T, const T& (*F)(const T&, const T&)>
struct opstack
{
deque<pair<T, T>> a;
size_t size() { return a.size(); }
bool empty() { return a.empty(); }
void push(T x)
{
if (size()) a.push_back({x, F(a.back().second, x)});
else a.push_back({x, x});
}
T top() { return a.back().first; }
T op() { return a.back().second; }
void pop() { a.pop_back(); }
void swap(opstack &x) { a.swap(x.a); }
};
template <typename T, const T& (*F)(const T&, const T&)>
struct opdeque
{
opstack<T, F> f, b, t;
void rebalance()
{
bool s = false;
if (b.empty()) { s = true; b.swap(f); }
int y = (b.size() / 2);
while (y--) { t.push(b.top()); b.pop(); }
while (b.size()) { f.push(b.top()); b.pop(); }
while (t.size()) { b.push(t.top()); t.pop(); }
if (s) b.swap(f);
}
size_t size() { return b.size() + f.size(); }
bool empty() { return size() == 0; }
void push_front(T x) { f.push(x); }
void push_back(T x) { b.push(x); }
T back()
{
if (b.empty()) rebalance();
return b.top();
}
T front()
{
if (f.empty()) rebalance();
return f.top();
}
void pop_back()
{
if (b.empty()) rebalance();
b.pop();
}
void pop_front()
{
if (f.empty()) rebalance();
f.pop();
}
T op()
{
if (f.empty()) return b.op();
if (b.empty()) return f.op();
return F(b.op(), f.op());
}
};
int n, k, a[N];
i64 dp[N][101];
int main()
{
memset(dp, 63, sizeof dp);
ShinLena;
cin >> n >> k;
for (int i = 0; i < n; ++i) cin >> a[i];
{
opstack<int, std::max> q;
for (int i = 0; i < n; ++i) q.push(a[i]), dp[0][i] = q.op();
}
for (int j = 1; j < k; ++j)
{
stack<int> q;
opdeque<pair<int, int>, std::min> w;
opdeque<int, std::min> y;
for (int i = 0; i < n; ++i)
{
while (q.size() && a[q.top()] < a[i]) q.pop();
if (q.size())
{
auto C = min(dp[j][q.top()], dp[j-1][q.top()] + a[i]);
while (w.size() && w.front().second <= q.top()) w.pop_front();
if (w.size()) C = min(C, 1ll * w.op().first + a[i]);
dp[j][i] = C;
}
else if (y.size())
{
dp[j][i] = y.op() + a[i];
}
w.push_back({dp[j-1][i], i});
y.push_back(dp[j-1][i]);
q.push(i);
}
}
for (int j = 0; j < k; ++j)
{
for (int i = 0; i < n; ++i)
{
//cout << dp[j][i] << " ";
}
//cout<<endl;
}
cout << dp[k-1][n-1];
return 0;
}
