#include <fstream>

using namespace std;

ifstream fin ("rucsac.in");
ofstream fout ("rucsac.out");

const int mxN = 5e3 + 1, mxG = 1e4 + 1, INF = INT_MIN;

int greu[mxN], prof[mxN], n, G, dp[mxN], vMax = 0;

int main(){
    fin >> n >> G;
    for(int i = 1; i <= n; i++)
        fin >> greu[i] >> prof[i];

    for(int i = 1; i <= G; i++)
        dp[i] = INF;

    dp[0] = 0;
    for(int i = 1; i <= n; i++)
        for(int g = G; g >= greu[i]; g--){
            if(dp[g - greu[i]] != INF){
                dp[g] = max(dp[g], dp[g - greu[i]] + prof[i]);
                vMax = max(vMax, G);
            }
        }

    fout << dp[vMax] << "\n";

    for(int i = 0; i <= G; i++)
        fout << dp[i] << " ";
}