/* 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;				// 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)); 	
						//Vectorul v pastreaza solutii partiale (intre indicii start si stop - simulare coada-)
	int pas = 0, start=0,stop =0;		// Pacurgem gutuile in ordinea stabilita, de la inaltimea cea mai mare, si incercam sa le culegem. 
						
	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);	// Daca gutuia i inca se afla la o inaltime la care ajunge Gigel
			++stop;
			++pas;				// adaugam valoarea greutatii ei in vectorul de solutii,
		}					//  pastrandu-l sortat crescator.
		else
			if(*(v+start) < gcrt)			// Daca greutatea gutuii curente este mai mare decat 
			{	++start;			//prima valoare din vectorul de solutii(sortat)
				insert(gcrt, v,start, stop);	// scoatem acea valoare din v (minimul) si inseram greutatea curenta.
				++stop;
				
			}
//		printf("v: ");
//		for(j=start;j<stop;j++)
//			printf("%lu ",*(v+j));
//		printf("\n");
	}
	

	for(i=start;i<stop; i++)	// Calculam greutatea totala a gutuielor culese, adunand valorile din v (intre indicii start-> stop)
		Gmax += *(v+i);

	free(v);			// Eliberare spatiu alocat
	free(g);
	free(h); 
	free(ord);
	v = g =  h = NULL;
	ord = NULL;
	//Afisare
	FILE *fout;
	fout = fopen("gutui.out","wt"); // deschidere fisier scriere
	fprintf(fout,"%lu", Gmax);	
	printf("%lu\n", Gmax);
	fclose(fout);			// inchidere fisier output
	return 0;
}