#include<bits/stdc++.h>
using namespace std;
struct node{int v,k;}dp[105][105];//k存上一次的拿书 
struct node2{int x,y;}a[100005];
int n,k,x,h[100005];
int f(int a,int b){if(a==b)return b-1;return b;}
int cmp(node2 a,node2 b){return a.x<b.x;}
int main()
    {
    cin>>n>>k;
    for(int i=1;i<=n;i++)cin>>a[i].x>>a[i].y;
    sort(a+1,a+n+1,cmp);
    for(int i=1;i<=n;i++)h[i]=a[i].y;
    for(int i=1;i<=n;i++)cout<<h[i]<<' ';
    for(int i=1;i<=n;i++)
        {
        for(int j=0;j<i;j++)
            {
            if(j>0&&i!=j+1)
				{
				//dp[i][j]=max(dp[i-1][j]+abs(h[i]-h[i-1]),dp[i-1][j-1]);
				if(dp[i-1][j].v+abs(h[i]-h[f(dp[i-1][j].k,i-1)])>dp[i-1][j-1].v){dp[i][j].v=dp[i-1][j-1].v;dp[i][j].k=i;}
				else {dp[i][j].v=dp[i-1][j].v+abs(h[i]-h[f(dp[i-1][j].k,i-1)]);dp[i][j].k=dp[i-1][j].k;}
				}
            else if(i!=j+1)
				{
				dp[i][j].v=dp[i-1][j].v+abs(h[i]-h[i-1]);dp[i][j].k=0;
				}
            else dp[i][j].v=dp[i][j].k=0;
            cout<<dp[i][j].v<<' ';
            }
        cout<<endl;
        }
    cout<<dp[n][k].v;
    return 0;
    }