#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

#define maxn 1010
#define LL(x) 2*x
#define RR(x) 2*x+1
#define M(x) (L[x]+R[x])/2
#define abs(x) ((x)<0?-(x):(x));

int sum[maxn][maxn];
int mst[maxn][maxn];
int dp[maxn][30];
int n,k,arr[maxn];

struct PartitionTree
{
    int L[maxn*2],R[maxn*2];
    int sorted[maxn];
    int val[20][maxn];
    int tol[20][maxn];

    void init()
    {
        for(int i=0;i<n;i++) val[0][i]=i;
        copy(arr,arr+n,sorted);
        sort(sorted,sorted+n);
        build(0,n);
    }
    void build(int l, int r,int d=0,int idx=1)
    {
        L[idx]=l;
        R[idx]=r;
        if(r-l==1) return;
        int m=M(idx),il=l,ir=m;
        int sameNum=sorted+m-lower_bound(sorted+l,sorted+m,sorted[m]);
        for(int i=l;i<r;i++)
        {
            tol[d][i]=il-l;
            if(arr[val[d][i]]==sorted[m]&&sameNum)
            {
                val[d+1][il++]=val[d][i];
                sameNum--;
            }
            else if(arr[val[d][i]]<sorted[m]) val[d+1][il++]=val[d][i];
            else val[d+1][ir++]=val[d][i];
        }
        build(l,m,d+1,LL(idx));
        build(m,r,d+1,RR(idx));
    }
    int query(int l,int r,int rank)
    {
        int a,b,d=0,idx=1;
        while(r-l>1)
        {
            a=tol[d][l];
            b=(r==R[idx]?M(idx)-L[idx]:tol[d][r])-a;
            if(rank<b)
            {
                l=L[idx]+a;
                r=l+b;
                idx=LL(idx);
            }
            else
            {
                l=M(idx)+l-L[idx]-a;
                r=M(idx)+r-L[idx]-a-b;
                rank=rank-b;
                idx=RR(idx);
            }
            d++;
        }
        return val[d][l];
    }
}pt;


int main()
{
    freopen("in","r",stdin);
    while(scanf("%d%d",&n,&k),n||k)
    {
        printf("%d %d\n",n,k);
        for(int i=0;i<n;i++) scanf("%d",arr+i);
        pt.init();
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<n;j++) sum[i][j]=abs(arr[j]-arr[i]);
            for(int j=1;j<n;j++) sum[i][j]+=sum[i][j-1];
        }
        for(int l=0;l<n;l++)
        {
            for(int r=l;r<n;r++)
            {
                int i=pt.query(l,r,(r-l)/2+1);
                mst[l][r]=sum[i][r]-sum[i][l-1];
            }
        }
        for(int l=0;l<n;l++,puts("")) for(int r=0;r<n;r++) printf("%d\t",mst[l][r]);
        memset(dp,63,sizeof(dp));
        dp[0][0]=0;
        for(int i=1;i<=k;i++)
            for(int j=0;j<n;j++)
                for(int w=0;w<j;w++)
                    dp[j][i]=min(dp[j][i],dp[w][i-1]+mst[w+1][i]);
        printf("%d\n",dp[n-1][k]);
    }
    return 0;
}