#include<bits/stdc++.h>
#define ll long long
#define el '\n'
#define rep(i,a,b) for (int i=a;i<=b;++i)
using namespace std;
ll n,k,a[100001],dp[101][100001],ma[22][100001];
ll get(ll l, ll r)
{
if (l>r) return 1e18;
ll k=log2(r-l+1);
return max(ma[k][l],ma[k][r-(1<<k)+1]);
}
void sol(ll g, ll l, ll r, ll ol, ll oR)
{
if (l>r) return;
ll mid=l+r>>1;
dp[g][mid]=1e18;
ll pos=0;
rep(i,1,mid)
{
ll newcost=dp[g-1][i]+get(i+1,mid);
//if (g==2 && mid==6) cout<<ol<<' '<<oR<<' '<<dp[g-1][i]<<' '<<get(i+1,mid)<<' '<<i+1<<el;
if (dp[g][mid]>newcost)
{
pos=i;
dp[g][mid]=newcost;
}
}
sol(g,l,mid-1,ol,pos);
sol(g,mid+1,r,pos,oR);
}
void solve()
{
cin>>n>>k;
rep(i,1,k) dp[0][i]=1e18;
rep(i,1,n)
{
cin>>a[i];
ma[0][i]=a[i];
}
for (int i=1;i<=log2(n);i++)
{
for (int j=1;j<=(n-(1<<i)+1);j++) ma[i][j]=max(ma[i-1][j],ma[i-1][j+(1<<(i-1))]);
}
rep(i,1,n)
{
dp[1][i]=get(1,i);
}
rep(i,2,k) sol(i,1,n,1,n);
cout<<dp[k][n];
}
int main()
{
solve();
return 0;
}
