#include <bits/stdc++.h>
using namespace std;
template<typename _Tp> bool minimize(_Tp& __a, const _Tp& __b) {if (__a > __b) {__a = __b; return true;} return false;}
template<typename _Tp> bool maximize(_Tp& __a, const _Tp& __b) {if (__a < __b) {__a = __b; return true;} return false;}
#define sp ' '
#define el '\n'
#define fi first
#define se second
#define pii pair<int, int>
#define ll long long
#define int long long
#define _HyG_ signed main()
#define MASK(i) (1LL << (i))
#define BIT(x, i) ((x>>i)&1)
#define SON(x, i) ((x) | MASK(i))
#define SOF(x, i) ((x) & ~MASK(i))
#define BIT_C(x) __builtin_popcountll(x)
#define fu(i,a,b) for(int i = a; i <= b; i++)
#define fd(i,a,b) for(int i = a; i >=b ; i--)
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define file(name) freopen(name".INP", "r", stdin); freopen(name".OUT", "w", stdout);
const int N = 1e5 + 5;
const int Log = 20;
const int MOD = 1e9 + 7;
const ll oo = 4485090715960753727;
const int base = 301;
const int so = (int)2e5;
int n, k, a[N], f[N][105];
void init()
{
cin>>n>>k;
fu(i, 1, n) cin>>a[i];
}
vector<vector<int>> Tree;
int MaxTree;
void update(int kk, int id, int l, int r, int pos, int vl)
{
if (pos > r && pos < l) return;
if (l == r)
{
Tree[id][kk] = min(Tree[id][kk], vl);
return;
}
else
{
int m =(l + r)/2;
update(kk, id * 2, l, m, pos, vl);
update(kk, id * 2 + 1, m + 1, r, pos, vl);
Tree[id][kk] = min(Tree[id * 2][kk], Tree[id * 2 + 1][kk]);
}
}
int query(int kk, int id, int l, int r, int u, int v)
{
if (r < u || l > v) return oo;
if (l >= u && r <= v) return Tree[id][kk];
else
{
int m = (l + r)/2;
int L = query(kk, id * 2, l, m, u, v);
int R = query(kk, id * 2 + 1, m + 1, r, u, v);
return min(L, R);
}
}
void process()
{
MaxTree = n;
Tree.resize(4 * MaxTree + 1);
fu(i, 0, 4 * MaxTree)
{
Tree[i].resize(k + 1);
fill(Tree[i].begin(), Tree[i].end(), oo);
}
memset(f, 0x3f, sizeof f);
stack<int> st;
f[0][1] = 0;
fu(i, 1, n)
{
while (st.size() && a[i] > a[st.top()]) st.pop();
fu(j, 1, k)
{
int l = 1;
if (st.size())
{
l = st.top();
f[i][j] = min(f[i][j], f[st.top()][j]);
}
if (j == 1)
{
f[i][j] = max(f[i - 1][j], a[i]);
}
else
{
int vl = query(j - 1, 1, 1, MaxTree, l, i - 1);
f[i][j] = min(f[i][j], vl + a[i]);
}
update(j, 1, 1, MaxTree, i, f[i][j]);
}
st.push(i);
}
cout<<f[n][k];
}
_HyG_
{
fast
//file("TREE");
int t = 1; //cin>>t;
while (t--)
{
init();
process();
}
return (0^0);
}
