#include <stdio.h>
#include <stdlib.h>

typedef struct info {
  int  satis;
  char get[1001];
} info;
info **cur_data;
int  n_children, limit;

void check_child (int nc, int pr, int ex, int fr) 
{
  info *ip, **new_data = calloc(1001,sizeof(info*));
  int  cx, new_cost, new_sat;

  for (cx = 0;  cx <= limit;  ++cx) {
    ip = cur_data[cx];
    if (ip) {
      printf("  Checking cost %d satisfaction %d...\n", cx, ip->satis);

      /* Assume gift: */
      new_cost = cx + pr;  new_sat = ip->satis + ex;
      if (new_cost > limit ||
	  new_data[new_cost] && new_data[new_cost]->satis >= new_sat) {
	/* Keep better distribution: */
	printf("    Giving does not improve solution.\n");
      } else {
	/* Improve distribution: */
	printf("    Giving improves situation to %d.\n", new_sat);
	if (! new_data[new_cost]) new_data[new_cost] = malloc(sizeof(info));
	*(new_data[new_cost]) = *ip;  new_data[new_cost]->satis = new_sat;
	new_data[new_cost]->get[nc] = 1;
      }

      /* Assume no gift: */
      new_sat = ip->satis - fr;
      if (new_data[cx] && new_data[cx]->satis >= new_sat) {
	/* Keep better distribution: */
	printf("    No gift does not improve solution.\n");
      } else {
	/* Improve distribution: */
	printf("    No gift improves situation to %d.\n", new_sat);
	if (! new_data[cx]) new_data[cx] = malloc(sizeof(info));
	*(new_data[cx]) = *ip;  new_data[cx]->satis = new_sat;
	new_data[cx]->get[nc] = 0;
      }

      free(ip);
    }
  }

  free(cur_data);  cur_data = new_data;
}


int main (void)
{
  FILE *in_f  = fopen("christmas.in","r"),
       *out_f = fopen("christmas.out","w");
  info *p;
  int  price, excit, frust, ch_ix, pix;

  printf("Starting...\n");
  fscanf(in_f, "%d%d", &n_children, &limit);

  printf("Initializing...\n");
  cur_data = calloc(1001, sizeof(info*));

  printf("Clearing data...\n");
  p = cur_data[0] = malloc(sizeof(info));  p->satis = 0;
  for (pix = 1;  pix <= n_children;  ++pix) p->get[pix] = 0;
  printf("Initialization done.\n");

  for (ch_ix = 1;  ch_ix <= n_children;  ++ch_ix) {
    fscanf(in_f, "%d%d%d", &price, &excit, &frust);
    printf("New child: price=%d, excitement=%d, frustration=%d.\n",
	   price, excit, frust);
    check_child(ch_ix, price, excit, frust);
  }

  /* Find best solution: */
  p = cur_data[0];
  for (ch_ix = 1;  ch_ix <= limit;  ++ch_ix) 
    if (cur_data[ch_ix] && cur_data[ch_ix]->satis > p->satis) 
      p = cur_data[ch_ix];

  fprintf(out_f, "%d\n", p->satis);
  for (ch_ix = 1;  ch_ix <= n_children;  ++ch_ix)
    fprintf(out_f, "%d", p->get[ch_ix]);
  fprintf(out_f, "\n");

  fclose(in_f);  fclose(out_f);  return 0;
}