#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
const int maxn = 1e5 + 7;
struct Fenwick_Tree_Min
{
vector <int> tree;
void init(int n) {tree.assign(n+4 , INF);}
void update(int pos , int val)
{
pos = (int)(tree.size()) - pos;
while(pos < (int)tree.size())
{
tree[pos] = min(tree[pos] , val);
pos += (pos & (-pos));
}
}
int get_suf(int pos)
{
pos = tree.size() - pos;
int res = INF;
while(pos > 0)
{
res = min(tree[pos] , res);
pos -= (pos & (-pos));
}
return res;
}
};
Fenwick_Tree_Min BIT[102];
int n , k , a[maxn] , Lnxt[maxn] , Rnxt[maxn] , dp[maxn][102];
void build()
{
for(int i = 0; i <= k; i++) BIT[i].init(n);
stack <int> st;
for(int i = 1; i <= n; i++)
{
while(!st.empty() && a[st.top()] <= a[i]) st.pop();
if(st.empty()) Lnxt[i] = 0;
else Lnxt[i] = st.top();
st.push(i);
}
while(!st.empty()) st.pop();
for(int i = n; i >= 1; i--)
{
while(!st.empty() && a[st.top()] <= a[i]) st.pop();
if(st.empty()) Rnxt[i] = n+1;
else Rnxt[i] = st.top();
st.push(i);
}
//test:
//for(int i = 1; i <= n; i++) cout << Lnxt[i] << ' '; cout << '\n';
//for(int i = 1; i <= n; i++) cout << Rnxt[i] << ' '; cout << '\n';
}
void solve()
{
cin >> n >> k;
for(int i = 1; i <= n; i++) cin >> a[i];
build();
int ans = INF;
for(int i = 1; i <= n; i++)
{
for(int j = min(i , k); j >= 2; j--)
{
dp[i][j] = BIT[j-1].get_suf(Lnxt[i] + 1) + a[i];
BIT[j].update(Rnxt[i] - 1 , dp[i][j]);
if(j == k && Rnxt[i] == n+1)
{
ans = min(ans , dp[i][j]);
}
}
if(Lnxt[i] == 0)
{
dp[i][1] = a[i];
BIT[1].update(Rnxt[i] - 1 , dp[i][1]);
if(k == 1 && Rnxt[i] == n+1) ans = min(ans , dp[i][1]);
}
}
cout << ans << '\n';
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
//freopen("inp.txt" , "r" , stdin);
//freopen("out.txt" , "w" , stdout);
solve();
return 0;
}
