#include <stdio.h>
#include <stdlib.h>
#define GMAX 10010

int maxim(int a,int b)
{
    if(a>b)
        return a;
    else
        return b;
}
int a[2][GMAX];
void rucsac(FILE *fis,FILE *gis)
{
    int n=0,g=0,i=0,*w=NULL,*p=NULL,l=0,j=0;
    fscanf(fis,"%d",&n);
    fscanf(fis,"%d",&g);
    w=(int*)malloc((n+1)*sizeof(int));
    if(w==NULL)
    {
        perror("eroare la alocarea dinamic\n");
        exit(-1);
    }
    p=(int*)malloc((n+1)*sizeof(int));
    if(p==NULL)
    {
        perror("eroare la alocarea dinamica\n");
        exit(-1);
    }
    for(i=1;i<=n;i++)
    {
        fscanf(fis,"%d",&w[i]);
        fscanf(fis,"%d",&p[i]);
    }
    for(i=1;i<=n;i++,l=1-l)
    {
        for(j=0;j<=g;j++)
        {
            printf("%d ", l);
            a[1-l][j]=a[l][j];
            if(w[i]<=j)
            {   
                a[1-l][j]=maxim(a[1-l][j],(a[l][j-w[i]]+p[i]));
            }
        }
    }
    fprintf(gis,"%d\n",a[l][g]);
    free(w);
    free(p);
}
int main(void)
{   
    FILE *fis=NULL,*gis=NULL;
    fis=fopen("rucsac.in","r");
    if(fis==NULL)
    {
        perror("eroare la deschidere fisier\n");
        exit(-1);
    }
    gis=fopen("rucsac.out","w");
    if(gis==NULL)
    {
        perror("eroare la deschidere fisier\n");
        exit(-1);
    }
    rucsac(fis,gis);
    fclose(fis);
    fclose(gis);

    return 0;
}