#include <fstream>

using namespace std;

ifstream fin("energii.in");
ofstream fout("energii.out");

int e[1002] , c[10002] , d[1002];

int main()
{
    int g,w;
    fin>>g>>w;
    for(int i=1;i<=g;i++)
        fin>>e[i]>>c[i];
    d[0]=1;
    for(int i=1;i<=g;i++)
    {
        for(int j=w;j>=0;j--)
        {
            if(d[j]>=1&&(j+e[i])>=w)
            {
                d[j+e[i]]=max(d[j+e[i]],c[i]+d[j]);
                fout<<d[j+e[i]]-1<<" ";
            }
        }
    }
}