#include<fstream>
#include<algorithm>

using namespace std;

class Object{
public:
    int weight;
    int profit;
    Object(int weight,int profit):profit(profit),weight(weight){}
    Object(const Object &copyO){
        this->weight = copyO.weight;
        this->profit = copyO.profit;
    }
};

bool invertCompareTo(Object *x, Object *y){

    return x->profit>y->profit;
}


Object *objects[5000], *bestSol[5000][2];
int n,gMax;

int main(){

    ifstream f("rucsac.in");
    ofstream g("rucsac.out");

    f>>n>>gMax;
    int w,p;

    for(int i=0; i<n; ++i){

            f>>w>>p;
            objects[i] = new Object(w,p);
    }

    sort(objects, objects+n, invertCompareTo);

    if(objects[0]->weight<gMax)
        bestSol[0][0] = objects[0];
    else
        bestSol[0][0] = new Object(0,0);

    for(int i=1; i<n; ++i){
        for(int j=0; j<i; ++j){ //we write last one in the end
            if( (bestSol[j][0]->weight + objects[i]->weight) <= gMax){
                bestSol[j][1] = new Object(bestSol[j][0]->weight + objects[i]->weight, bestSol[j][0]->profit + objects[i]->profit);
            }
            else
                bestSol[j][1] = bestSol[j][0];
        }

        if(objects[i]->weight<=gMax)
            bestSol[i][1] = objects[i];
        else
            bestSol[i][1] = new Object(0,0);

        for(int j=0; j<=i; ++j)
            bestSol[j][0]=bestSol[j][1];
    }

    for(int i=0; i<n;++i)
        g<<bestSol[i][0]->profit<<" ";


    f.close();g.close();
    return 0;
}