#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=1;i<=n;i++)
    {
        for(int i=weight[pos];i<=g;i++)
        {
            if(pack[0][i]>pack[0][i-weight[pos]]+val[pos])
            {
                pack[1][i]=pack[0][i];
            }
            else
            {
                pack[1][i]=pack[0][i-weight[pos]]+val[pos];
            }
        }
        for(int i=1;i<=g;i++)
        {
            fprintf(fout,"%d ",pack[1][i]);
            pack[0][i]=pack[1][i];
        }
        fprintf(fout,"\n");
        pos++;
    }
    fprintf(fout,"%d",pack[1][g]);
}