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

typedef struct
{
  float greutate;
  float valoare;
  
}OBIECT;

FILE *fin, *fout;
float best_value = 0, current_value = 0;

float back(float gmax, int nr_obiecte, OBIECT *items, int k)
{
  if (k == nr_obiecte)
    {
      if (current_value > best_value)
	{
	  best_value = current_value;
        }
      return best_value;
    }

  if (items[k].greutate <= gmax)
    {
      gmax = gmax - items[k].greutate;
      current_value = current_value + items[k].valoare;
      back(gmax,nr_obiecte, items,k+1);
      gmax = gmax + items[k].greutate;
      current_value = current_value - items[k].valoare;
    }

  back(gmax, nr_obiecte, items, k+1);
 
  return best_value;
}

void citire(int *nr_obiecte, float *gmax, OBIECT **items)
{
  if(fscanf(fin,"%d", nr_obiecte)!=1)
    {
      exit(-1);
    }
  
  if(fscanf(fin,"%f", gmax)!=1)
    {
      exit(-1);
    }

  if((*items = (malloc((*nr_obiecte)*sizeof(OBIECT)))) == NULL)
    {
      printf("Memorie insuficienta\n");
      exit(-1);
    }

  for(int i = 0; i<*nr_obiecte; i++)
    {
      if(fscanf(fin,"%f %f", &(*items)[i].greutate, &(*items)[i].valoare)!=2)
	{
	  exit(-1);
	}
    }
}

void afisare(float gmax, int nr_obiecte, OBIECT *items, int i)
{
  
  float x = back(gmax,nr_obiecte, items, 0);
  fprintf(fout,"%.2f", x);
    
}

int main(void)
{
  int nr_obiecte;
  float gmax;
  OBIECT *items = NULL;
  
  int i=0;
  
  if((fin = fopen("rucsacfr.in","r"))==NULL)
    {
      printf("Eroare deschidere fisier\n");
      exit(-1);
    }

   if((fout = fopen("rucsacfr.out","w"))==NULL)
    {
      printf("Eroare deschidere fisier\n");
      exit(-1);
    }
  
  citire(&nr_obiecte,&gmax,&items);
  afisare(gmax, nr_obiecte, items, i);

  free(items);
  fclose(fin);
  fclose(fout);

  return 0;
}