#include <fstream>
#include <cstring>


using namespace std ;

const int NMAX = 105 ;
const int GNMAX = 305 ;

ifstream cin("rucsac.in") ;
ofstream cout("rucsac.out") ;

int N, MAXG;
int C[NMAX], G[NMAX];
int CMax[GNMAX], Uz[GNMAX][NMAX];

inline void Rezolvare()
{

    //memset(CMax, -1, sizeof(CMax));

    for(int s = 1 ; s <= MAXG ; ++ s)
            for(int i = 1 ;i <= N ; ++ i)
                if(G[i] <= s && CMax[s - G[i]] != - 1 && !Uz[s - G[i]][i])
                    if(CMax[s] < C[i] + CMax[s - G[i]])
                        {CMax[s] = C[i]  + CMax[s - G[i]] ;
                        for(int k = 1 ; k <= N ; ++ k)
                            Uz[s][k] = Uz[s - G[i]][k];
                        Uz[s][i] = 1 ; }
}


int main()
{
    cin >> N >> MAXG;
    for(int i = 1 ;i <= N ; ++ i)
        cin >> G[i] >> C[i] ;
    Rezolvare();

    cout << CMax[MAXG] << '\n' ;
    for(int i = 1 ; i <= MAXG ; ++ i)
        cout << CMax[i] << '\n';

    cin.close();
    cout.close();
    return 0 ;
}