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

template<typename T> class tabu_list {
	private:
		T *elements;
		bool full;
		unsigned int position;
		unsigned int size;
	public:
		tabu_list(int s): full(false), position(0), size(s) {
			elements = new T[size];
		}
		~tabu_list(){
			delete [] elements;
		}
		void push(const T &new_element){
			if( position == size ){
				position = 0;
				full = true;
			}
			elements[position] = new_element; 
			position++;
		}
		void flush(void){
			full = false;
			position = 0;
		}
		bool operator[](const T &element){
			//unsigned int sum = 0;
			if( full ){
				for( unsigned int i = 0; i < size; i++ ){
					//if( elements[i] == element ) return true;
					//assert( (size + (i - position)) > 0 );
					if( elements[i] == element && 
					    i != position && 
					    !(position == size && i == 0)) return true;
				}
					//if( elements[i] == element && i != position) return 1;
					
			} else {
				for( unsigned int i = 0; i < position; i++ )
					if( elements[i] == element ) return true; //sum += position - i;
			}
			return false;
		}//*/
};

#define MAX_PREDMETU 64

struct predmet {int cena; int vaha;} predmety[MAX_PREDMETU];
int max_cena, pocet_predmetu, kapacita_batohu;
bool nejlepsi_stav[MAX_PREDMETU];

static int cena_stavu( bool stav[MAX_PREDMETU] ){
	int sum = 0;
	for( int i = 0; i < pocet_predmetu; i++ )
		if( stav[i] ) sum += predmety[i].cena;
	return sum;
}
static int vaha_stavu( bool stav[MAX_PREDMETU] ){
	int sum = 0;
	for( int i = 0; i < pocet_predmetu; i++ )
		if( stav[i] ) sum += predmety[i].vaha;
	return sum;
}

static void heuristic(void){
	/* kratkodoba pamet */
	tabu_list<int> tabu_predmety( (int)sqrt(pocet_predmetu*2.0) );
	tabu_list<int> tabu_hodnoty( 2*pocet_predmetu+2 );
	/* dlouhodoba pamet */
	int fin[MAX_PREDMETU];
	int fout[MAX_PREDMETU];
	int nezlepsuji = 0;
	////////////////////////////
	int cena_akt_stavu;
	int kroku = pocet_predmetu*pocet_predmetu*4;
	bool stav[MAX_PREDMETU];

	float prumerna_cena = 0; int predmetu_v_baglu = 0;

	for( int i = 0; i < pocet_predmetu; i++ ){
		if( predmety[i].vaha < kapacita_batohu ) prumerna_cena += predmety[i].cena;
		predmetu_v_baglu++;
		stav[i] = false;
		fin[i] = 0;
		fout[i] = 0;
	}
	prumerna_cena /= predmetu_v_baglu;

	max_cena = 0;

	while( kroku-- > 0 ){
		int nejlepsi_zmena = -1;
		int hodnota_nej_zmeny = -1000000;
		

		// Zkus vse zmenit
		for(int i = 0; i < pocet_predmetu; stav[i] = !stav[i], i++){
			stav[i] = !stav[i];

			if( vaha_stavu(stav) > kapacita_batohu ) continue;

			// spocitej cenu
			cena_akt_stavu = cena_stavu( stav );
			int hodnota = cena_akt_stavu;
		       	if( tabu_predmety[i] != 0 ) hodnota = 0;//hodnota -= prumerna_cena*pocet_predmetu;
			if( cena_akt_stavu > max_cena ) hodnota += 8*prumerna_cena*pocet_predmetu;
			
			if( tabu_hodnoty[hodnota>>2] ) continue;

			if( kroku < pocet_predmetu )
				hodnota += fin[i] > fout[i] ? fin[i] - fout[i] : fout[i] - fin[i];

			if( hodnota_nej_zmeny < hodnota ){
				hodnota_nej_zmeny = hodnota;
				nejlepsi_zmena = i;
			}
		}
		stav[nejlepsi_zmena] = !stav[nejlepsi_zmena];

		tabu_hodnoty.push(hodnota_nej_zmeny>>2);
		tabu_predmety.push(nejlepsi_zmena);

		for( int i = 0; i < pocet_predmetu; i++ )
			if( stav[i] ) fin[ i ]++;
			else fout[ i ]++;

		cena_akt_stavu = cena_stavu( stav );
		if( cena_akt_stavu >= max_cena ){
			max_cena = cena_akt_stavu;
			for( int i = 0; i < pocet_predmetu; i++ )
				nejlepsi_stav[i] = stav[i];

			nezlepsuji = 0;
		}

#if defined MER_PRUBEH
		//printf("%d ", cena_akt_stavu);
		printf("%d ", hodnota_nej_zmeny);
#endif

		if( nezlepsuji++ > pocet_predmetu ){
			// Okopiruj nejlepsi stav
			for( int i = 0; i < pocet_predmetu; i++ )
				stav[i] = nejlepsi_stav[i];

			// Najdi nejdyl sedici prvek a vyhod ho
			int max = -1, max_idx = -1; 
			for( int i = 0; i < pocet_predmetu; i++ )
				if( stav[i] ){
					if( max < fin[ i ]){
						max_idx = i;
						max = fin[ i ];
					}	
				}
			stav[ max_idx ] = false;
			fin[ max_idx ] /= 2;

			tabu_predmety.flush();
			for( int i = 0; i < pocet_predmetu; i++ )
				tabu_predmety.push(max_idx);

			max = -1; 
			for( int i = 0; i < pocet_predmetu; i++ )
				if( stav[i] ){
					if( max < fin[ i ]){
						max_idx = i;
						max = fin[ i ];
					}	
				}
			stav[ max_idx ] = false;
			fin[ max_idx ] /= 2;

			tabu_predmety.push(max_idx);
			nezlepsuji = 0;
		}
	}
}


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

#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);
#elif defined MER_PRUBEH
		printf("%d ", zadani);
		heuristic();
		printf("\n");
#else
		heuristic();
		printf("%d %d %d ", zadani, pocet_predmetu, max_cena);
		for(i = 0; i < pocet_predmetu; i++)
			printf(" %d", nejlepsi_stav[i] ? 1 : 0);
		printf("\n");
#endif
	}
	return 0;
}