#include <iostream>
#include<cstdio>
#define max(a,b) ((a)>(b) ? (a):(b))
FILE * f=fopen("rucsac.in","r");
FILE * g=fopen("rucsac.out","w");
int n,p;
struct pula {int x,y;}c[100];
int a[5001][10001];
void citire( )
{ int i,x1,y1;
    fscanf(f,"%d %d",&n,&p);
    for(i=1;i<=n;i++)
    {
        fscanf(f,"%d %d",&x1,&y1);
    c[i].x=x1;
    c[i].y=y1;
    }
}
using namespace std;
void rezolvare( )
{ int i,j,ok;
    for(i=1;i<=p;i++)
    {
        if(i==c[1].x)
            a[1][i]=c[1].y;
    }
    for(i=1;i<=n;i++)
    {
        for(j=0;j<=p;j++)
    { a[i][j]=a[i-1][j];
        if(j-c[i].x>=0)
        a[i][j]=max(a[i][j],a[i-1][j-c[i].x]+c[i].y);
    }
    }
}




int main()
{ int i,j;
//cout<<max(1,2);
citire( );
rezolvare( );
for(i=1;i<=n;i++)
{
    for(j=1;j<=p;j++)
    {
        cout<<a[i][j]<<" ";
    }
    cout<<endl;
}
fprintf(g,"%d",a[n][p]);
return 0;
}