#include <iostream>
#include <fstream>
#define N 10010

using namespace std;

int sol[N];

int main()
{
    ifstream fin("rucsac.in");
    ofstream fout("rucsac.out");
    int nr, maxWeight, price, weight, aux;
    fin >> nr >> maxWeight;
    for (int k=1; k<=nr; k++)
    {
        fin >> weight >> price;
        for (int i=maxWeight; i>=1; i--)
        {
            if (i - weight <= 0)
                aux = 0;
            else
                aux = i - weight;
            if (sol[aux] + price > sol[i] && (weight + aux <= i) )
                sol[i] = sol[aux] + price;
        }
        for (int i=1; i<=maxWeight; i++)
            cout << sol[i] << " ";
        cout << "\n";
    }
    fout << sol[maxWeight];
    return 0;
}