/*
	 * 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;
			
		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 ("gutui.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 = (H-minh)/U+1;
		//minh++;
		minh++;
		nivel	=	(long int *) calloc ((minh+5),sizeof(long int));
		//for (i=0; i<=minh; i++) nivel[i] = 	(long int *) calloc (minh+5,sizeof(long int));

		printf ("minh=%ld\n",minh);
		
		for (i=1; i<=minh; i++) nivel[i] = -1;

		for (i=0; i<N; i++)
		{
			// calculez nivelul
			aux = (H - h[i])/U + 1;
			if (aux>0)
			{
				printf ("Pun gutuia %ld pe nivelul %ld\n",i,aux);
				if (nivel[aux]==-1) { printf ("am pus-o\n"); nivel[aux] = i; }
				else
				{
					printf ("nu pot\n");
					for (j = aux-1; j>=0; j--)
						if (nivel[j]==-1)
						{
							printf ("am pus-o pe %ld\n",j);
							nivel[j] = i;
							break;
						}
				}
			}
		}
		
		printf ("%ld niveluri:\n",minh);
		for (i=1; i<=minh; i++)
		{
			if (nivel[i]!=-1)
				printf ("Nivelul %ld: %ld\n",i,w[nivel[i]]);
			else
				printf ("Nivelul %ld: %d\n",i,0);
		}
		
		
		for (i=1; i<=minh; i++)
		{
			if (nivel[i]!=-1)
			{
				//printf (" %ld ",nivel[i][0]);
				//for (j=1; j<=nivel[i][0]; j++)
				 if (h[nivel[i]]<=H) {
					printf ("Iau gutuia %ld de pe nivelul %ld\n",w[nivel[i]],i);
					gout += w[nivel[i]];
					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;
	}