#include <stdio.h>
#include <inttypes.h>
#include <time.h>

int pocet_predmetu, kapacita_batohu, zadani, ceny[64], vahy[64], sumcen[64];
int max_cena; uint64_t nejlepsi_stav;

struct predmet {int cena; int vaha; int poradi;} predmety[64], nej_predmet;

static int rad(const void *p1, const void *p2)
{
	struct predmet *b = (struct predmet*)p1, *a = (struct predmet*)p2;
	return b->cena - a->cena;
}

void r2(int vaha, int cena, int zanoreni, uint64_t stav){
	if( zanoreni < pocet_predmetu ){
		if( cena + sumcen[zanoreni] < max_cena ) return;
		r2(vaha, cena, zanoreni + 1, stav);
		vaha += predmety[zanoreni].vaha;
		if( vaha <= kapacita_batohu ){
			cena += predmety[zanoreni].cena; stav |= (1 << predmety[zanoreni].poradi);
			r2(vaha, cena, zanoreni + 1, stav);
			if( cena > max_cena ){ max_cena = cena;	nejlepsi_stav = stav; }
		}
	} else {
		vaha += predmety[zanoreni].vaha;
		if( vaha <= kapacita_batohu ){
			cena += predmety[zanoreni].cena;
			if( cena > max_cena ){ max_cena = cena;	nejlepsi_stav = stav | (1<< predmety[zanoreni].poradi); }
		}
	}
}

int main(int argc, char *argv[])
{
	int i;
	while( scanf("%d%d%d", &zadani, &pocet_predmetu, &kapacita_batohu) == 3 ){
		for(i = 0; i < pocet_predmetu; i++)
			scanf("%d%d", &predmety[i].vaha, &predmety[i].cena), predmety[i].poradi = i;
		for(sumcen[pocet_predmetu - 1] = predmety[pocet_predmetu - 1].cena, i = pocet_predmetu - 2; i >= 0; i--)
			sumcen[i] = predmety[i].cena + sumcen[i+1]; 
#ifdef MER_CAS
		int opakovani = argc == 2 ? atoi(argv[1]) : MER_CAS, cas1, cas2; pocet_predmetu--;
		cas1 = clock();
		for(i = opakovani; i > 0; i--){ 
			qsort( predmety, pocet_predmetu + 1, sizeof(struct predmet), rad); 
			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	
		qsort( predmety, pocet_predmetu, sizeof(struct predmet), rad);
		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;
}