#include <iostream>
#include <fstream>
#include <cmath>
using namespace std;
int n, A[5001][10001], G;
ifstream in("rucsac.in");
ofstream out("rucsac.out");
int k = 1;
pair<int, int> V[101];
int main()
{
    in >> n >> G;
    for(int i = 1; i <= n; i++) {
        in >> V[i].first >> V[i].second;
    }
    for(int i = 0; i <= G; i++) {
        if(V[1].first <= i) A[1][i] = V[1].second;
    }
    for(int i = 2; i <=n; i++) {
        for(int j = 0; j <= G; j++) {
            //if(j==0) A[i][j] = 0;
            if(V[i].first <= j) {
                A[i][j] = max(A[i-1][j], A[i-1][j-V[i].first] + V[i].second);
            }
        }
    }

    for(int i = 1; i <= n; i++) {
        for (int j = 0; j <= G; j++) {
            cout << A[i][j] << ' ';
        }
        cout << endl;
    }
    return 0;
}