#include <bits/stdc++.h>
	
#define INF 23000
	
using namespace std;
	
 
	
int max1(int a, int b) { return (a > b) ? a : b; }
	
int n, W, val[1002], wt[1002], a[1001][5002];
	
 
	
int knapSack(int W, int wt[], int val[], int n)
	
{
    if (n == 0 || W == 0)
	
        return -1;
	
    if (wt[n - 1] > W)
        return knapSack(W, wt, val, n - 1);
   else
	
        return max1(val[n - 1] + knapSack(W - wt[n - 1],wt, val, n - 1),knapSack(W, wt, val, n - 1));
	
}
	
 
	
 
	
int main()
	
{
	
 
	
    freopen("energii.in", "r", stdin);
	
    freopen("energii.out", "w", stdout);
	
    int s;
	
    scanf("%d %d",&n,&W);
	
    for(int i = 1; i <= n; i++) {
	
        scanf("%d %d",&wt[i],&val[i]);
	
    }
	
 
	
    for(int i = 1; i <= n;i++) {
	
        for(int j = 1; j <= W;j++) {
	
                 s = INF;
	
            for(int k = 1; k <= n ;k++) {
	
                if(wt[k] <= j) {
	
 
	
                    if(s > (val[k] + a[i-1][j - wt[k]]))
	
                        s = val[k] + a[i-1][j - wt[k]];
	
 
	
                }
	
 
	
            }
	
             if(s  == INF)
             	s = 0;
             if( s > a[i-1][j] && i > 1 && j > 1)
             	s = a[i-1][j];
             

            a[i][j] = s;
	
        }
	
    }
	
 
   printf("%d",a[n][W]);

		
		for(int i = 1; i <= n; i++)	{

			for(int j = 1; j <= W; j++) {
				cout << a[i][j] << " ";

			}
			cout << endl;
		} 
    return 0; 
	
}