#include <bits/stdc++.h>
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define int long long
using namespace std;
const int INF = 1e18;
int n, s;
int a[100001], l[100001], mn[100001];
int dp[100001][2];
signed main(){
IOS;
cin >> n >> s;
for (int i = 1; i <= n; i++)
cin >> a[i];
for (int i = 1; i <= n; i++) {
for (l[i] = i - 1; l[i] > 0 && a[l[i]] <= a[i];)
l[i] = l[l[i]];
}
memset(dp, 0x3f, sizeof dp);
dp[1][1] = a[1];
for (int i = 2; i <= n; i++) dp[i][1] = max(dp[i - 1][1], a[i]);
for(int k=2;k<=s;k++)
{
mn[k-1]=dp[0][0];
for(int i=1;i<=n;i++)
dp[i][k&1]=dp[0][0];
for(int i=k;i<=n;i++)
{
mn[i]=dp[i-1][(k-1)&1];
for(int j=i-1;j > l[i];j=l[j])
mn[i]=min(mn[i],mn[j]);
dp[i][k&1]=min(dp[l[i]][k&1],mn[i]+a[i]);
}
}
cout<<dp[n][s&1];
}
