void dcn(ll i,ll l,ll r,ll opl,ll opr,vl& psum,vl& ausum,vvl& dp){
  if(l>r)return;

  ll mid=(l+r)/2;
  pl x={INF64,l};
  for(ll j=opl;j<min(mid,opr);j++){ 
    ll sum=dp[i-1][j-1] + ausum[j+1]-ausum[mid+1]-(mid-j)*psum[mid+1];
    // cout<<j<<" ";
    if((sum)<x.fi){
      x.fi=sum;
      x.se=j-1;
    }
  }
  // cout<<i<<" "<<mid<<" "<<x.se<<" "<<endl;
  dp[i][mid]=x.fi;
  dcn(i,l,mid-1,opl,x.se,psum,ausum,dp);
  dcn(i,mid+1,r,x.se,opr,psum,ausum,dp);


}
 
void chal(){
  ll n,k;
  cin>>n>>k;
  vl aa(n+1);
  Fo(i,1,n+1){
    cin>>aa[i];
  }
  vl psum(n+5,0);
  psum[n]=aa[n];
  Fo(i,n-1,-1){
    psum[i]+=(psum[i+1]+aa[i]);
  }
  debug(aa);
  debug(psum);
  vl ausum(n+5,0);
  ausum[n]=aa[n];
  Fo(i,n-1,0){
    ausum[i]=ausum[i+1]+psum[i];
  }
  debug(ausum);
  vvl dp(k+5,vl(n+5));
  Fo(i,1,n+1){
    dp[1][i]=ausum[2]-ausum[i+1]-(i-1)*psum[i+1];
  }
  Fo(i,2,k+1){
    dcn(i,1,n,1,n,psum,ausum,dp);
  }
  debug(dp);
  cout<<dp[k][n]<<endl;

  
  
  

  
  
 

}