#include <stdio.h>
#include <stdlib.h>
#include <time.h>
struct predmet {int cena; int vaha; int poradi;} predmety[40];

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

int main(int argc, char *argv[])
{
	int pocet_predmetu, kapacita_batohu, zadani;
	int vaha, cena;
	int i;
	unsigned long long ber;

	while( scanf("%d%d%d", &zadani, &pocet_predmetu, &kapacita_batohu) == 3 ){
		ber = vaha = cena = 0;
		for(i = 0; i < pocet_predmetu; i++){
			scanf("%d%d", &predmety[i].vaha, &predmety[i].cena);
			predmety[i].poradi = i;
		}
#ifdef MER_CAS
		int opakovani=OPAKOVANI, cas2, cas1;
		cas1 = clock();
		while(opakovani--){
#endif
		qsort( predmety, pocet_predmetu, sizeof(struct predmet), rad);
		for(i = 0; i < pocet_predmetu; i++)
			if( vaha + predmety[i].vaha <= kapacita_batohu ){
				vaha += predmety[i].vaha;
				cena += predmety[i].cena;
				ber |= 1 << predmety[i].poradi;
			}
#ifdef MER_CAS
		}
		cas2 = clock();
		printf("%f\n", ((cas2-cas1)/1000.0)/OPAKOVANI);
#else
		printf("%d %d %d ", zadani, pocet_predmetu, cena);
		for(i = 0; i < pocet_predmetu; i++)
			printf(" %d", ber&(1<<i)?1:0);
		printf("\n");
#endif
	}
	return 0;
}