# include <bits/stdc++.h>
using namespace std;
#define int long long
int k,n,a[100005],dp[100005][105],b[400005][105],l[100005],res;
stack<int> g;
void update(int id, int l, int r, int pos, int kk, int val)
{
if (pos < l or r < pos) return;
if (l==r)
{
b[id][kk] = val;
return;
}
int mid = (l+r)/2;
update(id*2,l,mid,pos,kk,val); update(id*2+1,mid+1,r,pos,kk,val);
b[id][kk] = min(b[id*2][kk],b[id*2+1][kk]);
}
int get(int id, int l, int r, int u, int v, int kk)
{
if (r < u or v < l) return 1e9;
if (u <= l and r <= v)
{
return b[id][kk];
}
int mid = (l+r)/2;
int q = get(id*2,l,mid,u,v,kk), p = get(id*2+1,mid+1,r,u,v,kk);
return min(p,q);
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> k;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
}
for (int i = 1; i <= n; i++)
{
while (!g.empty() and a[g.top()] <= a[i]) g.pop();
if (g.empty()) l[i] = 0;
else l[i] = g.top();
g.push(i);
}
for (int i =0; i <= n; i++) for (int j = 0; j <= k; j++) dp[i][j] = 1e9;
dp[0][0] = 0;
dp[1][1] = a[1];
update(1,1,n,1,1,dp[1][1]);
for (int i = 2; i <= n; i++)
{
dp[i][1] = max(dp[i-1][1],a[i]);
update(1,1,n,i,1,dp[i][1]);
}
for (int i = 1; i <= n; i++)
{
for (int j = 2; j <= k; j++)
{
// dp[i][j] = min(dp[l[i]][j-1],dp[p][j-1] + a[i] (p thuoc {l[i]+1,i}));
dp[i][j] = dp[l[i]][j];
if (l[i] <= i-1)
{
dp[i][j] = min(dp[i][j],get(1,1,n,max(l[i],j-1),i-1,j-1)+a[i]);
}
update(1,1,n,i,j,dp[i][j]);
}
}
// dp[i][j] la so tien nho nhat xet den vi tri i va da chia dc j doan
cout << dp[n][k];
}
