/* 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( *(h+i) < *(h+j) )
		return 1;
	if( *(h+i) == *(h+j) )			// si apoi dupa inaltimea la care se afla gutuia.
	{	
			return 0;
	}
	return -1;	
	
}

void insert(unsigned long int gcrt,unsigned long int *v, int start, int stop)
{	printf("insereaza g=%lu in v %i -> %i \n", gcrt, start, stop);
	if( start == stop)
		*(v+start)=gcrt;
	int i = stop-1;
	if(gcrt > *(v+stop-1))
	{	*(v+ stop) = gcrt;
		return;
	}
	while(gcrt < *(v+i) && i>= start)
	{	*(v+i+1) = *(v+i);
		i--;
	}
	*(v+i+1)=gcrt;
}

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 inaltime si greutate
						//( 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");
	unsigned long int *v = (unsigned long int *) calloc(N, sizeof(unsigned long int)); 

	int pas = 0, start=0,stop =0;
	for(i=0;i<N;i++)
	{	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(H >= hcrt + pas*U)
		{	insert(gcrt, v,start, stop);
			++stop;
			++pas;
		}
		else
			if(*(v+start) < gcrt)
			{	++start;
				insert(gcrt, v,start, stop);
				++stop;
				
			}
//		printf("v: ");
//		for(j=start;j<stop;j++)
//			printf("%lu ",*(v+j));
//		printf("\n");
	}
	

	for(i=start;i<stop; i++)
		Gmax += *(v+i);
/*
	free(&v);
	free(&g);
	free(&h);
	free(&ord);
*/	
	//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;
}