#include <fstream>
#define INF 2000000000
using namespace std;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
int n, g;
struct {
short gr, prof;
} ob[5001];
struct {
short viz;
int loc;
} rucsac[10001];;

int main()
{
    fin>>n>>g;
    for(int i=1;i<=n;i++)
        fin>>ob[i].gr>>ob[i].prof;

    for(int i=1;i<=g;i++)
        rucsac[i].loc=-INF;
    rucsac[0].viz=0;

    for(int k=1;k<=n;k++)
    {
        for(int i=0;i<g;i++)
            if(rucsac[i].loc!=-INF and rucsac[i].viz!=k)
            if(i+ob[k].gr<=g)
            if(rucsac[i+ob[k].gr].loc<rucsac[i].loc+ob[k].prof)
            {
                rucsac[i+ob[k].gr].loc=rucsac[i].loc+ob[k].prof;
                rucsac[i+ob[k].gr].viz=k;
            }
    }

    for(int i=0;i<=g;i++)
        fout<<rucsac[i].loc<<' ';
    return 0;
}