/*
	 * Gutu Marius Gabriel
	 * 321CA
	 * 
	 * Proiectarea Algoritmilor
	 * Tema 1
	 * Gutui
	 */
	
	#include <stdio.h>
	#include <stdlib.h>
	#include <math.h>
	
	#define INF	320
	
	int main()
	{
		/* Variabile principale */
		long int 
			N,	// numarul de gutui din copac
			H,	// inaltimea maxima la care ajunge Gigel
			U;	// cu cat se ridica crengile copacului dupa culegerea unei gutui
			
		long int
			*h,		// vectorul de inaltimi ale gutuilor
			*w,		// vectorul de greutati ale gutuilor
			nivel[INF][INF];
			
		long int
			gout;	// greutatea maxima a gutuilor pe care le poate culege Gigel
			
		long int 
			i, j, 	// contoare auxiliare
			sortat,
			minh,
			aux;
		
		// fisierele de intrare si de iesire
		FILE *fin, *fout;
		fin = fopen ("gutui2.in","r");
		fout = fopen ("gutui.out","w");
		
		// citim N, H si U
		fscanf(fin,"%ld %ld %ld",&N,&H,&U);
		
		// alocam spatiu pentru vectorul de greutati si pentru cel de 
		// inaltimi
		w	=	(long int *) calloc (N,sizeof(long int));
		h	=	(long int *) calloc (N,sizeof(long int));
		
		// citim perechile corespunzatoare inaltime-greutate pentru 
		// fiecare gutuie
		for (i=0; i<N; i++)
			fscanf(fin,"%ld %ld",&h[i],&w[i]);
		
		// setam greutatea maxima pe care o poate obtine Gigel la 0
		gout	=	0;
				
		// sortare dupa greutati
		sortat = 0;
		do
		{
			sortat = 1;
			for (i=0; i<N-1; i++)
				if (w[i]<w[i+1])
				{
					sortat = 0;
					aux = w[i];
					w[i] = w[i+1];
					w[i+1] = aux;
					aux = h[i];
					h[i] = h[i+1];
					h[i+1] = aux;
				}
				else if (w[i]==w[i+1])
				{
					// sortez dupa h
					if (h[i]<h[i+1])
					{
						sortat = 0;
						aux = w[i];
						w[i] = w[i+1];
						w[i+1] = aux;
						aux = h[i];
						h[i] = h[i+1];
						h[i+1] = aux;
					}
				}
		} while (sortat == 0);
		
		minh	=	INF;
		for (i=0; i<N; i++)
		{
			if (h[i] < minh)
				minh = h[i];
			printf ("%ld\tw=%ld\th=%ld\t\n",i,w[i],h[i]);
		}
		minh = (long int)((H-minh)/U) + 1;
		//minh++;
		/*minh++;
		nivel	=	(long int **) malloc ((minh+5)*sizeof(long int *));
		for (i=0; i<N; i++) nivel[i] = 	(long int *) calloc (minh+5,sizeof(long int));*/

		printf ("minh=%ld\n",minh);

		for (i=0; i<N; i++)
		{
			// calculez nivelul
			aux = (long int)((H - h[i])/U);
			aux++;
			if (aux>=0)
			{
				printf ("Cresc nivelul la %ld pentru gutuia %ld (avem %ld elem)\n",aux,i,nivel[aux][0]);
				nivel[aux][0]++;
				nivel[aux][nivel[aux][0]] = i;
			}
		}
		
		printf ("%ld niveluri:\n",minh);
		for (i=0; i<=minh; i++)
		{
			printf ("Nivelul %ld (%ld gutui): ",i,nivel[i][0]);
			for (j=1; j<=nivel[i][0]; j++)
				printf ("%ld ",w[nivel[i][j]]);
			printf ("\n");
		}
		
		
		for (i=0; i<=minh; i++)
		{
			if (nivel[i][0])
			{
				for (j=1; j<=nivel[i][0]; j++)
				 if (h[nivel[i][j]]<=H) {
					printf ("Iau gutuia %ld de pe nivelul %ld\n",w[nivel[i][j]],nivel[i][0]);
					gout += w[nivel[i][j]];
					H -= U;
				}
			}
		}
		
		// afisam greutatea maxima pe care o poate culege Gigel in fisier
		fprintf (fout,"%ld\n",gout);
		
		// inchidem fisierele
		fclose(fin);
		fclose(fout);
		return 0;
	}