// ProbLema rucsacuLui, dinamica O(N*G) timp, O(N) memorie
#include <iostream>
#include <cstdio>
//#include <algorithm>

using namespace std;

int N, G, Pmax;
int W[5010], P[5010];
int D[2][10010];

int main()
{
    freopen("rucsac.in", "r", stdin);
    //freopen("rucsac.out", "w", stdout);

    // Citire
    scanf("%d%d", &N, &G);
    for(int i = 1; i <= N; ++i)
        scanf("%d%d", &W[i], &P[i]);

    // Dinamica D[i][cw] - profituL maxim pe care-L putem obtine adaugand o submuLtime a primeLor i obiecte, insumand greutatea cw
    // Din aceasta dinamica vom tine uLtimeLe doua Linii, astfeL: Linia L va fi cea pe care avem soLutia pentru aL (i-1)-Lea eLement,
    // in timp ce  pe Linia 1-L vom construi soLutia pentru eLementuL i.
    int L=0;
    for(int i = 1; i <= N; ++i, L = 1 - L)
        for(int cw = 0; cw <= G; ++cw)
        {
            // Mai intai nu punem obiectuL i.
            D[1-L][cw] = D[L][cw];

            // Daca acest Lucru duce La o soLutie curenta mai buna, adaugam obiectuL i La o soLutie anterioara.
            if(W[i] <= cw)
                D[1-L][cw] = max(D[1-L][cw], D[L][cw - W[i]] + P[i]);
        }

    // SoLutia se va afLa in statea D[N][G], adica pe Linia L, La coLoana G
    Pmax = D[L][G];

        for(int cw = 0; cw <= G+1; ++cw)
            cout<<D[L][cw]<<' ';
        for(int cw = 0; cw <= G+1; ++cw)
            cout<<D[1-L][cw]<<' ';
        cout<<'\n';

    // Afisare
    printf("%d\n", Pmax);

    return 0;
}