#define GMAX 1001
#define PMAX 5001
#include <iostream>
#include <fstream>
using namespace std;

ifstream f1("energii.in");
ofstream f2("energii.out");

int G,P;
struct date
{
    int e,c;
};
date obiecte[GMAX];
int rucsac[PMAX];
int main()
{
    f1>>G>>P;
    for(int i=1;i<=G;i++)
    {
        f1>>obiecte[i].e>>obiecte[i].c;
    }
    for(int i=1;i<=P;i++)
        rucsac[i]=10002;
    for(int j=1;j<=G;j++)
    {
        for(int i=P;i>=obiecte[j].e;i--)
        {
            int val=rucsac[i-obiecte[j].e]+obiecte[j].c;
            if(val<rucsac[i]) rucsac[i]=val;
        }
        for(int i=1;i<=P;i++)
            cout<<rucsac[i]<<" ";
        cout<<endl;
    }
    f2<<rucsac[P];
    return 0;
}