/*
TASK:bus
LANG:C++
*/
#include <stdio.h>
#include <iostream>
#include <fstream>
#include <string>
#include <sstream>
#include <algorithm>
#include <vector>
#include <set>

#define MP make_pair
#define x first
#define y second
#define PB push_back
#define ALL(v) v.begin(),v.end()
#define VI vector<int>
using namespace std;

int n,k;
int d[1024][1024],c[1024],mb[1024][1024],mf[1024][1024];

int main()
{
    int i,j,l;
    scanf("%d%d",&n,&k);
    for (i=0; i<n; i++)
        scanf("%d",&c[i]);
    
    for (i=0; i<n; i++)    
     for (j=i+1; j<n; j++)
      mb[i][j]=mb[i][j-1]+c[j]*(j-i);
    for (i=n-1; i>=0; i--)    
     for (j=i-1; j>=0; j--)
      mf[j][i]=mf[j+1][i]+c[j]*(i-j);
      /*
   for (i=0; i<n; i++)
   {
    for (j=i; j<n; j++)
     cout<<mf[i][j]<<" ";
     cout<<endl; }*/
     
    for (i=1; i<n; i++)
     d[i][1]=1000000000;
    
    int pos,sp,mm;
    for (pos=1; pos<n; pos++)
     for (sp=2; sp<=k; sp++)
     {
           mm=1000000000;
           for (i=sp-2; i<pos; i++)
            mm <?= d[i][sp-1]+mb[i][(pos+i)/2]+mf[(pos+i)/2+1][pos];
           d[pos][sp]=mm; 
     }
    
    for (i=2; i<=k; i++){
     for (j=0; j<n; j++)
      cout<<d[j][i]<<" ";
     cout<<endl; }
     
     cout<<mb[1][n/2]<<" + "<<mf[n/2+1][n-1]<<endl;
    
    mm=1000000000;
    for (i=2; i<=k; i++)
     mm <?= d[n-1][i];
     
    printf("%d\n",mm); 
    
    
    return 0;
}
