/* 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 inaltime
	if( *(h+i) < *(h+j) )
		return 1;

	if( *(h+i) == *(h+j) )			// Utilizare: qsort
		return 0;
						
	return -1;	
	
}

void insert(unsigned long int gcrt,unsigned long int *v, int start, int stop)
{
	if( start == stop)		// Daca vectorul nu contine niciun element
	{	*(v+start)=gcrt; 	// insereaza gcrt in v. 
		return;
	}
	int i = stop-1;			// Parcurgere inversa v:
	if(gcrt > *(v+stop-1))		// daca valoarea retinuta de gcrt este mai mare decat ultima valoare din vectorul sortat,
	{	*(v+ stop) = gcrt;	// inseram gcrt pe ultima pozitie in vector;
		return;
	}					//altfel,
	while(gcrt < *(v+i) && i>= start)	// cat timp elementul curent din v are valoarea mai mare decat greutatea gutuii curente
	{	*(v+i+1) = *(v+i);		// mutam elementul din v cu o pozitie la dreapta si ne deplasam in stanga
		i--;				// pana gasim pozitia favorabila pentru a mentine vectorul v ordonat.
	}
	*(v+i+1)=gcrt;				// Inseram greutatea gcrt pe pozitia gasita .
}

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 

	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;		// Parcurgem gutuile in ordinea stabilita la sortare, de la inaltimea cea mai mare,
						// si incercam sa le culegem. 
	for(i=0;i<N;i++)			
	{	gcrt = *(g+ *(ord+i));	// greutatea gutuii de pe pozitia i in multimea sortata
		hcrt = *(h+ *(ord+i));  // inaltimea gutuii 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;
				
			}

	}
	

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

	// Eliberare spatiu alocat
	free(v);			
	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;
}