/*
		MARIN VIOLETA
		325 CA
		TEMA 1 - PROBLEMA 2
*/	

#include <stdio.h>
#include <stdlib.h>

/*
structura "gut" retine pentru fiecare gutuie nivelul si greutatea;
nivelul este definit in felul urmator: 
	o gutuie care trebuie culeasa la primul pas (altfel se va afla la o inaltime prea mare)
	se afla pe nivelul 1;
	o gutuie care trebuie culeasa la al doilea pas cel tarziu (altfel se va afla la o 
	inaltime prea mare) se afla pe nivelul 2; etc.
gutuile care se afla la inaltimi mai mari decat inaltimea maxima la care poate ajunge Gigel
vor avea nivelul 0;
*/ 
struct gut{
	unsigned int level;	
	unsigned int weight;
	};

/*
vectorul "gutui", format din structuri "gut", va retine toate gutuile "citite" din fisierul de intrare;
*/ 
struct gut *gutui;

/*
functie folosita la sortarea gutuilor;
acestea se sorteaza crescator, in functie de nivel;
daca nivelele mai multor gutui sunt egale, acestea sunt puse in ordinea descrescatoare a greutatilor;
*/  
int compare (const void * a, const void * b)
{
	if ((*(struct gut*)a).level == (*(struct gut*)b).level)	
		return -((*(struct gut*)a).weight - (*(struct gut*)b).weight); 
	 return ((*(struct gut*)a).level - (*(struct gut*)b).level); 	
}

/*
In continuare, 3 functii necesare structurii de min-heap pe care am folosit-o;
functia "parent" returneaza indicele parintelui nodului primit ca argument;
complexiatet: O(1);
*/  
unsigned int parent(unsigned int i){
	if (i % 2 == 0) return (i/2 - 1);
		else return i/2;
}

/*
functia "insert" insereaza pe ultima pozitie nodul cu greutate w si ii gaseste locul in heap;
se fac interschimbari succesive intre nod si parintele sau pana se respecta ordinea din heap;
complexitate: O(log n), unde n este numarul de elemente total al heapului;
complexitatea este aceasta, doarece, in cel mai defavorabil caz, se parcurg  toate nivelele,
pentru a gasi locul potrivit nodului nou inserat, iar heap-ul are [log n] nivele; 
*/
void insert(unsigned int w, unsigned int *heap, unsigned int pos){
heap[pos] = w;
unsigned int aux;
while ((pos > 0) && (heap[pos] < heap[parent(pos)])) {
					aux = heap[parent(pos)];
					heap[parent(pos)] = heap[pos];
					heap[pos] = aux;
					pos = parent(pos);
					}  
}

/*
functia "minheapify" gaseste locul noii radacini a heapului;
nodul curent se compara cu succesorii sai si se interschimba cu minimul dintre acestia; 
complexiate O(log n), unde n = numarul de elemente total al heapului;
in cel mai defavorabil caz, se parcug toate nivelele heapului;
*/ 
void minheapify(unsigned int *heap, unsigned int i, unsigned int length){

unsigned int l = 0, r = 0, least, aux;
if ((2 * i + 1) < length) l = 2 * i + 1;
if ((2 * i + 2) < length) r = 2 * i + 2;
if ((l == 0) || (r == 0)) return;
	else
	if ((l != 0) && (r == 0))
		{
		if (heap[l] < heap[i]) {
					aux = heap[i];
					heap[i] = heap[l];
					heap[l] = aux;
					minheapify(heap, l, length);
					}
				else return;
		}
	 else
		{
		if (heap[l] > heap[r]) least = r;
			else least = l;
		if (heap[i] > heap[least]) {
					  aux = heap[i];
					  heap[i] = heap[least];
					  heap[least] = aux;
					  minheapify(heap, least, length);	
					   }
		else return;	 	
  		}
}


int main(){
	unsigned int i, k, t;
	unsigned int h,u,n;	
	unsigned int level,no_levels, min_level = 0xffffffff;
	unsigned int max = 0;
	
	FILE *f = fopen("gutui.in","r");
	fscanf(f, "%u", &n);
	fscanf(f, "%u", &h);
	fscanf(f, "%u", &u);
	
	gutui = (struct gut *)malloc(n * sizeof(struct gut));
	
	/*
	se citesc datele pentru fiecare gutuie;
	min_level va contine de fapt inaltimea minima dintre inaltimile valide ale tuturor gutuilor citite;
	min_level va fi folosit la calcularea numarului total de pasi;
	*/
	for (i = 0; i < n; i++)
		{
		fscanf(f, "%u", &level);
		fscanf(f, "%u", &gutui[i].weight);
		if (level > h) gutui[i].level = 0;
			else
			{
			gutui[i].level = (h - level)/u + 1 ;
			if (min_level > level) min_level = level;
			}
		}
	fclose(f);

	/*
	se sorteaza gutuile in ordinea specificata in functia "compare";
	Complexitate qsort : O(n * log n);	
	*/
	qsort(gutui, n, sizeof(struct gut), compare);
	
	/*
	se calculeaza numarul total de pasi pe care il va face Gigel;
	in cazul in care nicio inaltime a gutuilor nu a fost valida, numarul de pasi va fi 0;
	*/
	if (min_level != 0xffffffff)
 		no_levels = (h - min_level)/u + 1;
		else 
		no_levels = 0;

	/*
	daca numarul total de pasi este 0, greutatea maxima va fi 0 si programul se incheie;
	*/
	if (no_levels == 0) 	{
			 	f = fopen("gutui.out", "w");
				fprintf(f, "%u\n", max);
				fclose(f);
				return 0; 	
				}
	/*
	heapul nu poate avea mai multe elemente decat numarul total de pasi, adica decat numarul
	total de gutui culese;
	*/
	unsigned int * heap = (unsigned int *)calloc(no_levels,sizeof(unsigned int));
	
	level = 0; k = 0;  t = 0; 	

	/*
	se parcurg toate gutuile (care sunt sortatea in felul descris anterior) si se incearca pentru fiecare gutuie,
	sa se gaseasca un loc in heap;
	heapul va contine la final greutatile gutuilor culese;
	k contorizeaza numarul de gutui de pe un anumit nivel;
	t contorizeaza numarul de gutui introduse in heap la un moment dat;
	level este nivelul curent;
	Complexitate totala : O(n * log n), deoarece se parcurg toate gutuile, o singura data, si pentru fiecare gutuie,
	cea mai costisitoare operatie care poate fi efectuala este apelul functiei "insert" sau a functiei "minheapify",
	iar aceste functii au complexitatea O(log n);
	*/ 
	for (i = 0; i < n; i++){
		if (gutui[i].level > level) {
						/*
						am gasit un nou nivel;
						k = 1; este sigur o gutuie pe acest nivel;
						pasul curent se acutalizeaza;  
						*/
						level = gutui[i].level;
						k = 1;
					   }
						else
						
						k = k + 1;
		/*
		nivelul curent este egal cu nivelul gutuii anterioare;
		contorizam gutuile de pe acest nivel;
		daca sunt mai multe gutui pe acest nivel decat cate pot fi culese,
		ele nu ne mai intereseaza;
		*/  
		if ((gutui[i].level != 0)&&(k <= gutui[i].level)){
						/* 	
						daca numarul de gutui din heap este mai mic decat pasul curent,
						gutuia poate fi culeasa fara probleme;
						o inseram in heap si actualizam greutatea totala "max", dar si 
						numarul total de gutui culese;
						*/  
						if (t < level) {
								t = t + 1;
								insert(gutui[i].weight, heap, t - 1);
								max = max + gutui[i].weight; 
								   }
							else
							/* 
							numarul de gutui din heap este mai mare sau egal cu pasul curent;
							gutuia nu va fi culeasa decat daca greutatea sa este mai mare
							decat minimul greutatilor gutuilor culese;
							*/ 	
							  {
							if (heap[0] < gutui[i].weight) {
											/*
											se actualizeaza greutatea totala "max"
											si se pastreaza relatia de ordine in heap;
											*/
											max = max - heap[0] + gutui[i].weight;	
											heap[0] = gutui[i].weight;
											minheapify(heap, 0, level);
											}
							  }
						}
					
		}	 
								    
						
	
	f = fopen("gutui.out", "w");
	fprintf(f, "%u\n", max);
	fclose(f);

	free(gutui);
	free(heap);
	
return 0;
}