/*
	 * Gutu Marius Gabriel
	 * 321CA
	 * 
	 * Proiectarea Algoritmilor
	 * Tema 1
	 * Gutui
	 */
	
	#include <stdio.h>
	#include <stdlib.h>
	#include <math.h>
	
	/* Infinit */
	#define INF	2000000000

	/* Structura unei gutui */
	typedef struct
	{
		long int h;	// inaltimea
		long int w;	// greutatea
	} gutuie;
	
	gutuie *gut;	// vectorul de gutui
	
	// Functie de comparare a doua elemente
	int compare (const void * a, const void * b)
	{
		// Daca am gutui la aceeasi inaltime, sortez descrescator dupa 
		// inaltime; daca nu, sortez descrescator dupa greutate
		if(((gutuie *)a)->h != ((gutuie *)b)->h)
			return ((gutuie*)b)->w - ((gutuie*)a)->w;
		//return ((gutuie*)b)->h - ((gutuie*)a)->h;	  
	}
		
	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
			gout;	// greutatea maxima a gutuilor pe care le poate culege Gigel
			
		long int 
			i, j, 	// contoare auxiliare
			minh,	// valoare axuliara
			aux;	// valoare axuliara
			
		long int
			*nivel;	// vector de "nivele" pentru gutui == de cate ori ar
					// putea fi luata o anumita gutuie pentru a se incadra
					// in limita impusa de H
		
		// 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 gutui
		gut	=	(gutuie *) malloc (N*sizeof(gutuie));
		
		// citim perechile corespunzatoare inaltime-greutate pentru 
		// fiecare gutuie
		for (i=0; i<N; i++)
			fscanf(fin,"%ld %ld",&gut[i].h,&gut[i].w);
		
		// setam greutatea maxima pe care o poate obtine Gigel la 0
		gout	=	0;
				
		// sortare vector de gutui cu un algoritm QuickSort
		qsort(gut, N, sizeof(gutuie), compare);
		
		// setam minimul global la INF
		minh	=	INF;
		
		// pentru fiecare gutuie
		for (i=0; i<N; i++)
		{
			// daca se afla la o inaltime mai mica decat minh
			if (gut[i].h < minh)
				// actualizam minh
				minh = gut[i].h;
		}
		minh = (H-minh)/U+1;
		nivel	=	(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 - gut[i].h)/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,gut[nivel[i]].w);
			else
				printf ("Nivelul %ld: %d\n",i,0);
		}
		
		
		for (i=1; i<=minh; i++)
		{
			if (nivel[i]!=-1)
			{
				 if (gut[nivel[i]].h<=H) {
					printf ("Iau gutuia %ld de pe nivelul %ld\n",gut[nivel[i]].w,i);
					gout += gut[nivel[i]].w;
					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;
	}