#include <iostream>
#include <fstream>

using namespace std;

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

int n, gm;
int castig=0;

struct obiect{
  int g, v;
}o[20000];

void citire()
{
    int i;
    fin>>n>>gm;
    for(i=1;i<=n;i++)
    {
        fin>>o[i].g>>o[i].v;
    }
}

void sortare()
{
    int i,j;
    for(i=1;i<n;i++)
        for(j=1+i;j<=n;j++)
            if(o[i].v<o[j].v)
                swap(o[i],o[j]);
}

int alegere()
{
    int i;
    cout<<n<<" ";
    for(i=1;i<=n && gm!=0;i++)
    {
        if(o[i].g<=gm)
        {
            gm=gm-o[i].g;
            castig=castig+o[i].v;
        }
        cout<<castig<<" ";
    }
    return castig;
}

int main()
{
    citire();
    sortare();
    fout<<alegere();
    return 0;
}