#include <stdio.h>
#include <inttypes.h>
#include <sys/times.h>
#include <time.h>

int pocet_predmetu, kapacita_batohu, zadani, ceny[32], vahy[32];
int max_cena;
uint32_t nejlepsi_stav;

void r2(int vaha, int cena, int zanoreni, uint32_t stav){
	if( zanoreni < pocet_predmetu ){
		r2(vaha, cena, zanoreni + 1, stav);
		vaha += vahy[zanoreni];
		if( vaha <= kapacita_batohu ){
			cena += ceny[zanoreni]; stav |= (1 << zanoreni);
			r2(vaha, cena, zanoreni + 1, stav);
			if( cena > max_cena ){ max_cena = cena;	nejlepsi_stav = stav; }
		}
	} else {
		vaha += vahy[zanoreni];
		if( vaha <= kapacita_batohu ){
			cena += ceny[zanoreni];
			if( cena > max_cena ){ max_cena = cena;	nejlepsi_stav = stav | (1<<zanoreni); }
		}
	}
}

int main(void)
{
	int i;
	while( scanf("%d%d%d", &zadani, &pocet_predmetu, &kapacita_batohu) == 3 ){
		for(i = 0; i < pocet_predmetu; i++)
			scanf("%d%d", vahy + i, ceny + i);
#ifdef MER_CAS
		int opakovani = OPAKOVANI; pocet_predmetu--;
		int cas1, cas2;
		cas1 = clock();
		while(opakovani--){
			max_cena = 0; nejlepsi_stav = 0;  
			r2(0, 0, 0, 0);
		}
		cas2 = clock();
		printf("%f\n", ((cas2-cas1)*1000.0/CLOCKS_PER_SEC)/OPAKOVANI);
#else	
		max_cena = 0; nejlepsi_stav = 0; pocet_predmetu--; 
		r2(0, 0, 0, 0);
		printf("%d %d %d ", zadani, pocet_predmetu + 1, max_cena);
		for(i = 0; i < pocet_predmetu + 1; i++)
			printf(" %d", nejlepsi_stav & (1 << i) ? 1 : 0);
		printf("\n");
#endif
	}
	return 0;
}