#include <fstream>
# include <math.h>

using namespace std;

// Problema rucsacului
// Se da o multime formata din N obiecte, fiecare fiind caracterizat de o greutate si un profit. Sa se gaseasca o submultime de obiecte astfel incat suma profiturilor lor sa fie maxima, iar suma greutatilor lor sa nu depaseasca o valoare G.

// Date de intrare
// Pe prima linie a fişierul rucsac.in se vor gasi valorile N si G, cu semnificatia din enunt. Pe urmatoarele N linii se vor gasi perechile de valori Wi si Pi, reprezentand greutatea, respectiv profitul obiectului i.

// Date de ieşire
// In fişierul de ieşire rucsac.out se va afisa o singura valoare Pmax, profitul maxim care poate fi obtinut respectand conditia problemei.

// Restricţii
// 1 ≤ N ≤ 5000
// 1 ≤ G ≤ 10000
// 0 ≤ Wi, Pi ≤ 10000

int N, G, W[10000], P[10000], sol[10000], st[10000], P_sol;

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

// In final, putem optimiza codul.
// Prima etapa ar fi ordonarea obiectelor, in functie de greutate.

// int Write_sol () {
//   if P_temp > P_sol {
//     P_sol = P_temp;
//     for (int i=0; i<N, i++)
//       sol(i) = st[i];
//   }
// }

void Tipar(){
  cout << P_sol;
  cout << "\n";
  for ( int i = 0; i < N; i ++ )
    cout << sol[i] << ", ";
}

void back1(int k0, int W_temp, int P_temp) {
  if (k0 == N) { // am ajuns la capat
    if (P_temp > P_sol) {
      P_sol = P_temp;
      for (int i=0; i<N; i++)
        sol[i] = st[i];
    }
  } else {
    for (int k = k0; k<N; k++) {
      if (W_temp + W[k] <= G) {
//        W_temp = W_temp + W[k];
//        P_temp = P_temp + P[k];
        st[k] = 1;
        back1(k+1, W_temp + W[k], P_temp + P[k]);
      } else
        back1(k+1, W_temp, P_temp);
      st[k] = 0;
    }
  }
}

int main(){
  // N = numarul total de obiecte
  // G = Greutatea maxima din rucsac
  // Ar trebui sa verific datele de intrare.
  // Memoria ar trebui alocata dinamic.
  cin >> N >> G;
  for (int i=0; i<N; i++)
    cin >> W[i] >> P[i];
  int k0 = 0, W_temp = 0, P_temp = 0;
  back1(k0, W_temp, P_temp);
  Tipar();
  return 0;
}