#include <stdio.h>
#include <stdlib.h>
#define max(a,b) (a > b ? a : b)
#define min(a,b) (a < b? a : b)
#define MAX 10001
#define CAP_MAX 10001
int n, GT;
int castig[MAX], greutate[MAX];
int v[2][MAX];

void readInput (){
    int i;
    ///printf("Numarul de obiecte: ");
    scanf("%d", &n);
    /// printf("Capacitatea rucsacului: ");
    scanf("%d", &GT);


    for (i = 1; i <= n; i++){
        ///printf("Greutate[%d] = ", i);
        scanf("%d", &greutate[i]);
        ///printf("Castig[%d] = ", i);
        scanf("%d", &castig[i]);

    }
}
void Run (){
    int i, j, k;

    for ( i = 0; i <= GT; i++)
        v[0][i] = 0;

    for ( i = 1; i <= n; i++){
        for ( j = 1; j <= GT; j++)
            if ( greutate[i] <= j )
                 v[1][j]= max(v[0][j],v[0][j - greutate[i]]+ castig[i]);

        for ( k = 1; k <= GT; k++){
            printf("%d ", v[1][k]);
            v[0][k]=v[1][k];
        }
        printf("\n");
    }

    printf("%d", v[1][GT]);
}
int main()
{
    freopen("rucsac.in","r",stdin);
    freopen("rucsac.out","w",stdout);
    readInput();
    Run();
    return 0;
}