#include <bits/stdc++.h>

using namespace std;
ifstream fi("rucsac.in");
ofstream fo("rucsac.out");
int n,g,w,p;
int lcurent=1;
int A[2][100005];

int main()
{
    fi>>n>>g;
    for(int i=1; i<=n; i++)
    {
        fi>>w>>p;
        for(int j=1; j<=g; j++)
        {
            cout<<lcurent<<" ";
            A[lcurent][j]=A[1-lcurent][j];
            if(w<=j)
                A[lcurent][j]=max(A[1-lcurent][j],A[1-lcurent][j-w]+p);
        }
        lcurent=1-lcurent;
    }
    fo<<A[n%2][g]<<" ";
    fi.close();
    fo.close();
    return 0;
}