#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N=1e5+5;
const int K=105;
const ll oo=(long double)1e18+1;
int n,k;
int a[N];
namespace sub4
{
const int oo=1e9+1;
int ma;
int dp[N],opt[N];
stack <int> st;
void solve()
{
ma=0;
for (int i=1;i<=n;i++)
{
ma=max(ma,a[i]);
dp[i]=ma;
}
for (int rep=2;rep<=k;rep++)
{
while (!st.empty()) st.pop();
for (int i=rep;i<=n;i++)
opt[i]=dp[i-1];
for (int i=rep;i<=n;i++)
{
while (!st.empty() and a[st.top()]<=a[i])
{
opt[i]=min(opt[i],opt[st.top()]);
st.pop();
}
dp[i]=opt[i]+a[i];
if (!st.empty()) dp[i]=min(dp[i],dp[st.top()]);
st.push(i);
}
}
cout << dp[n];
}
}
int main()
{
ios_base::sync_with_stdio(NULL);
cin.tie(NULL); cout.tie(NULL);
cin >> n >> k;
for (int i=1;i<=n;i++)
cin >> a[i];
sub4::solve();
}
