#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define fast ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define exit return 0
#define cap pair<int,int>
#define fi first
#define se second
#define pb push_back
#define FOR(i,l,r) for(int i=l;i<=r;i++)
#define FOD(i,r,l) for(int i=r;i>=l;i--)
#define fill(f,x) memset(f,x,sizeof(f))
#define lcm(a,b) (a/__gcd(a,b)*b)
#define TIME 1.0 * clock() / CLOCKS_PER_SEC
int n,g;
int cur[1000005];
int prevv[1000005];
int prefix[1000005];
int A[1000005];
int st[20][200005];
int calc(int l, int r)
{
int lg=log2(r-l+1);
return max(st[lg][l],st[lg][r-(1<<lg)+1]);
}
void solve(int l, int r, int optl, int optr)
{
if(l>r) return;
int mid=(l+r)>>1;
cap best={1e18,-1};
FOR(i,optl,min(optr,mid-1))
{
best=min(best,{prevv[i]+calc(i+1,mid),i});
}
cur[mid]=best.first;
int opt=best.second;
solve(l,mid-1,optl,opt);
solve(mid+1,r,opt,optr);
}
signed main()
{
fast;
cin>>n>>g;
FOR(i,1,n)
{
cin>>A[i];
prefix[i]=prefix[i-1]+A[i];
}
FOR(i,1,n)
{
st[0][i]=A[i];
}
int lg=log2(n);
FOR(i,1,lg)
{
FOR(j,1,n-(1<<i)+1) st[i][j]=max(st[i-1][j],st[i-1][j+(1<<(i-1))]);
}
prevv[0]=0;
//cout<<calc(1,1)<<endl;
FOR(i,1,n) prevv[i]=1e18;
FOR(i,0,n) cur[i]=1e18;
FOR(i,1,g)
{
solve(1,n,0,n);
FOR(j,0,n) prevv[j]=cur[j];
// FOR(j,0,n) cout<<cur[j]<<" ";
// cout<<endl;
}
cout<<cur[n];
exit;
}
/*
░▒▓███████▓▒░░▒▓█▓▒░░▒▓█▓▒░▒▓███████▓▒░ ░▒▓██████▓▒░
░▒▓█▓▒░░▒▓█▓▒░▒▓█▓▒░░▒▓█▓▒░▒▓█▓▒░░▒▓█▓▒░▒▓█▓▒░░▒▓█▓▒░
░▒▓█▓▒░░▒▓█▓▒░▒▓█▓▒░░▒▓█▓▒░▒▓█▓▒░░▒▓█▓▒░▒▓█▓▒░
░▒▓█▓▒░░▒▓█▓▒░▒▓█▓▒░░▒▓█▓▒░▒▓█▓▒░░▒▓█▓▒░▒▓█▓▒▒▓███▓▒░
░▒▓█▓▒░░▒▓█▓▒░▒▓█▓▒░░▒▓█▓▒░▒▓█▓▒░░▒▓█▓▒░▒▓█▓▒░░▒▓█▓▒░
░▒▓█▓▒░░▒▓█▓▒░▒▓█▓▒░░▒▓█▓▒░▒▓█▓▒░░▒▓█▓▒░▒▓█▓▒░░▒▓█▓▒░
░▒▓███████▓▒░ ░▒▓██████▓▒░░▒▓█▓▒░░▒▓█▓▒░░▒▓██████▓▒░
*/
