/* SOCEA Raluca, 324 CB, PA - Tema 1 */

// Problema 2: Gutui

#include<stdio.h>
#include<stdlib.h>
unsigned long int *h, *g;

int compare (const void * a, const void * b)  // Functia compare foloseste criteriul de comparare 
{
	int i = *(int*)a, j = *(int *)b;	// descrescator dupa greutate
	if( *(g+i) < *(g+j) )
		return 1;
	if( *(g+i) == *(g+j) )			// si apoi dupa inaltimea la care se afla gutuia.
	{	if( *(h+i) < *(h+j) )
			return 1;
		if( *(h+i) == *(h+j) )		// Utilizare: qsort
			return 0;
	}
	return -1;	
	
}


int main()
{	
	unsigned long int H, U, Gmax=0, gcrt, hcrt;
	int N;

	// Citire
	FILE *fin;			// deschidere fisier intrare
	fin = fopen("gutui.in","rt");
	fscanf(fin,"%i %lu %lu",&N, &H, &U);	
	
	// Alocare vectori de dimensiune N (greutatile si inaltimile gutuielor)	
	g = (unsigned long int *) calloc(N, sizeof(unsigned long int));
	h = (unsigned long int *) calloc(N, sizeof(unsigned long int));

	int *ord = (int *) calloc(N, sizeof(int)); // Vectorul ord retine indici de la 0->n-1; Initial ord[i] = i;
						// dupa sortare ord[i] = k are semnificatia:  in vectorul ordonat dupa criteriul din functia compare, 
	int i,j;				// pe pozitia i se afla elementul cu indicele k din lista initiala.
	for(i=0;i<N;i++)
	{	fscanf(fin,"%lu %lu",h+i, g+i);	// citirea inaltimii si greutatii pentru fiecare gutuie
		*(ord+i) = i;			// initializare vector ord
	}
	
	fclose(fin);  	// inchidere fisier intrare

	qsort(ord, N, sizeof(int), compare);	//sortare in ordine descrescatoare dupa greutate si dupa inaltime 
						//( se va modifica ordinea indicilor din vectorul ord, vectorii g si h raman neschimbati) 
/*	for(i=0;i<N;i++)
		printf("%i ", *(ord+i)+1 );
	printf("\n");
*/
	int *v = (int *) calloc(N, sizeof(int)); // Vectorul v[i] retine cu cati pasi s-a cules gutuia i inainte de a se ridica creanga prea sus
	for(i=0;i<N;i++)			 // pentru ca Gigel sa nu o mai poata ajunge ( Daca H = 100 si U = 10, iar h[i] = 75, iar gutuia i e
		*(v+i) = -1;			// prima culeasa, v[i] = 2. Daca se mai culegeau 2 gutui inainte, gutuia i s-ar fi aflat la h = 95.
						// Daca a 3-a gutuie aleasa nu ar fi fost gutuia i, Gigel n-ar mai fi putut sa o ajunga ). 
/*	for(i=0;i<N;i++)			
		printf("%i ", *(v+i) );
	printf("\n");
*/
	int  stop = -1;
	unsigned long int niv = 0;
	for(i=0; i<N;i++)		//Luam pe rand toate gutuile descrescator dupa greutate si, apoi, inaltime. 
	{	gcrt = *(g+ *(ord+i));	// greutatea de pe pozitia i in multimea sortata
		hcrt = *(h+ *(ord+i));  // inaltimea de pe pozitia i in multimea sortata
		if(hcrt > H)
			*(v+i) = -2;	// daca inaltimea curenta depaseste inaltimea maxima, v[i] = -2.
		else
			if( H < niv*U + hcrt)  // daca dupa cele niv gutui deja culese, gutuia i nu poate fi ajunsa
			{		
				if(stop == -1)		// v[i] ramane -1.
					stop = i;	// stop pastreaza pozitia primei gutui care n-a fost culeasa, in multimea sortata
				else continue;
			}
			else
			{//	printf("niv: %i  H-niv*U: %lu  hcrt: %i   v[i]: %i", niv, H-niv*U,hcrt, *(v+i));  
				*(v+i) = (H-niv*U -hcrt)/U; 		// Daca gutuia poate fi culeasa, se actualizeaza v[i].
			//	printf("-> v[i] modificat: %i \n", *(v+i));
				Gmax += gcrt;
				niv++;	
			}
		
	}

	// Pana aici, am folosit un algoritm Greedy. Sorteaza gutuile si le selecteaza pe cele cu greutatea mai mare, cat timp ajunge la ele.

	// In continuare, cautam printre gutuile ramase sa vedem daca ar fi putut fi culese intr-un pas intermediar.

	for(i=0;i<N;i++)
		printf("%i ", *(v+i) );
	printf("\n%lu\n", Gmax);
//	printf("\nniv: %i\n", niv);
//	printf("\nstop: %i\n", stop);
	int min, k , re, gasit;
	
	for(i=stop; i< N; i++)
	{	
		while(*(v+i)!= -1 && i<N)		// Daca v[i] = -1, analizam cazul gutuii curente.
			i++;
		if(i==N)
			break;

		hcrt = *(h+ *(ord+i));		 // inaltimea gutuii curente
		min = 	N;	
		j = N-1;	
		re = niv;	// retine indicele gutuii(in ordinea culegerii) dupa care incercam intercalarea culegerii gutuii de pe pozitia i.
		gasit = 1;
		while( *(v+j)!=0 && H < re*U + hcrt && j>=0)
		{				// Parcurgem vectorul v de la coada utilizand contorul j. 
			if( *(v+j)>0)		// Daca inainte de j mai putem lua o gutuie (crengile nu se ridica a.i. sa afecteze gutuile deja culese)
			{	re--;		// adica v[j] > 0, atunci 
				*(v+j) = *(v+j) - 1;
				if(*(v+j) < min)	// actualizam v[j]
					min = *(v+j); 
			}
			
			j--;
			if(*(v+j)==0)
				gasit=0;	
		}
		
				
		if( gasit )			// Daca am gasit o solutie de a culege si gutuia i, actualizam greutatea totala (Gmax)
		{	
			Gmax += *(g+ *(ord+i)); // v[i] si numarul de gutui culese (niv) 
			*(v+i) = min;
			niv++;
		}
		else
		for(k = j+1; k<N;k++)
				if(*(v+k)>=0)
					(*(v+k))++;
		
	}

	for(i=0;i<N;i++)
		printf("%i ", *(v+i) );	
		
	
	//Afisare
	FILE *fout;
	fout = fopen("gutui.out","wt"); // deschidere fisier scriere
	fprintf(fout,"%lu", Gmax);	
	printf("\n%lu\n", Gmax);
	fclose(fout);			// inchidere fisier output
	return 0;
}