#include<stdio.h>

int pack[2][10001],weight[10001],val[10001],pos=1;

int main()
{
    FILE *fin,*fout;
    fin=fopen("rucsac.in","r");
    fout=fopen("rucsac.out","w");

    int n,g;
    fscanf(fin,"%d %d",&n,&g);
    for(int i=1;i<=n;i++)
    {
        fscanf(fin,"%d %d",&weight[i],&val[i]);
    }
    for(int i=weight[pos];i<=g;i++)
    {
        pack[0][i]=val[pos];
    }
    pos++;
    for(int i=0;i<=n;i++)
    {
        for(int j=weight[pos];j<=g;j++)
        {
            if(pack[0][j]>pack[0][j-weight[pos]]+val[pos])
            {
                pack[1][j]=pack[0][j];
            }
            else
            {
                pack[1][j]=pack[0][j-weight[pos]]+val[pos];
            }
        }
        for(int j=1;j<=g;j++)
        {
            fprintf(fout,"%d ",pack[1][i]);
            pack[0][i]=pack[1][i];
        }
        fprintf(fout,"\n");
        pos++;
    }
    fprintf(fout,"%d",pack[1][g]);
}