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

struct predmet {int cena; int vaha; int poradi;} predmety[64];
int max_cena, pocet_predmetu, kapacita_batohu; unsigned long long stav;

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;
}

void heuristic(void){
	int vaha = 0, i; stav = 0, max_cena = 0;
	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;
			max_cena += predmety[i].cena;
			stav |= 1 << predmety[i].poradi;
		}
}


int main(int argc, char *argv[])
{
	int zadani, 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;
		}

#ifdef MER_CAS
		int opakovani = argc == 2 ? atoi(argv[1]) : MER_CAS, cas1, cas2;
		cas1 = clock();
		for(i = opakovani; i > 0; i--) heuristic();
		cas2 = clock();
		printf("%f\n", ((cas2-cas1)*1000.0/CLOCKS_PER_SEC)/opakovani);
#else
		heuristic();
		printf("%d %d %d ", zadani, pocet_predmetu, max_cena);
		for(i = 0; i < pocet_predmetu; i++)
			printf(" %d", stav & (1<<i) ? 1 : 0);
		printf("\n");
#endif
	}
	return 0;
}