#include <cstdio>
#include <algorithm>

using namespace std;

struct obj{
    int w, p;
};

obj object[5001];

int n;

int dinam[10001];

const int inf = 500000000;

int main()
{
    freopen ("rucsac.in", "r", stdin);
    freopen ("rucsac.out", "w", stdout);
    int G;
    scanf("%d%d", &n ,&G);
    for(int i = 1; i <= n; i++)
        scanf("%d%d", &object[i].w, &object[i].p);
    dinam[0] = 0;
    for(int i = 1; i <= G; i++)
        dinam[i] = -inf;
    for(int i = 1; i <= n; i++){
        for(int j = G; j >= object[i].w; j--){
            dinam[j] = max(dinam[j], dinam[j - object[i].w] + object[i].p);
        }
        for(int j = 0; j <= G; j++){
            if(dinam[j] >= 0)
                printf("%d ",dinam[j]);
            else
                printf("- ");
        }
        printf("\n");
    }
    int rez = 0;
    for(int i = 1; i <= G; i++)
        if(dinam[i] > rez)
            rez = dinam[i];
    printf("%d", rez);
    return 0;
}