#include <cstdio>

#define inFile  "energii.in"
#define outFile "energii.out"

#define NMAX    1005
#define GMAX    5005

#define max(a,b)    (a>b?a:b)

int n, g;
int d[NMAX][GMAX];

int main() {
    freopen(inFile, "r", stdin);
    freopen(outFile, "w", stdout);

    scanf("%d %d", &n, &g);

    d[n][g] = -1;

    for(int i = 1, j, ei, ci, a, b; i <= n; i++) {
        scanf("%d %d", &ei, &ci);
        for(j = 1; j <= g; j++) {
            if(ei <= j) {
                d[i][j] = max(d[i-1][j], ci + d[i-1][j-ei]);
            } else {
                d[i][j] = d[i-1][j];
            }
        }
    }

    for(int i = 1, j; i <= n; i++) {
        for(j = 1; j <= g; j++) {
            printf("%d\t", d[i][j]);
        }
        printf("\n");
    }

    return 0;
}