#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <limits.h>

int N;      //numarul de gutui din copac
int H;		//inaltimea maxima la care ajunge Gigel
int U;		//cu cat se ridica crengile copacului dupa culegerea unei gutui
int* height;    //inaltimile
int* weight;	//greutatile gutuilor
int** values;	//valorile de pe fiecare nivel
int* nr_values;	//numarul de valori de pe fiecare nivel

int greutate_max;   //greutatea maxima a gutuilor culese

//intoarce minimum valorilor
int min(int a, int b)
{
	if(a < b) {
		return a;
	} else {
		return b;
	}
}

//citeste din fisier matricea de 0/1
void citeste(char* nume_fisier)
{
	int i,row;		  //iteratori
	char line[512];   //retine o linie citita
	FILE* in = fopen(nume_fisier,"r"); //deschide fisier
	if(in == NULL) {   //daca nu s-a putut deschide fisierul afiseaza eroare
		printf("Fisierul de intrare nu a putut fi gasit\n");
		exit(1);
	}
	fgets(line,512,in);   //citeste prima linie
	N = atoi((char*)strtok(line," "));     //retine numarul de gutui din copac
	H = atoi((char*)strtok(NULL," "));		//retine inaltimea maxima la care ajunge Gigel
	U = atoi((char*)strtok(NULL," "));		//retine cu cat se ridica crengile copacului dupa culegerea unei gutui
	
	height = (int*)malloc(sizeof(int)*N); //aloca memorie pentru inaltimi
	weight = (int*)malloc(sizeof(int)*N); //aloca memorie pentru greutati
	values = (int**)malloc(sizeof(int*)*(H/U)+1);	//aloca memorie pentru valorile de pe fiecare nivel
	nr_values = (int*)malloc(sizeof(int)*(H/U)+1);	//aloca memorie pentru valori

	//pentru fiecare interval
	for(row=0;row<H/U+1;row++) {
		nr_values[row] = 0;
	}

	for(i=0;i<N;i++) { //pentru fiecare gutuie
		fgets(line,512,in);	 //citeste linia
		height[i] = atoi((char*)strtok(line," "));	//retine inaltimea
		weight[i] = atoi((char*)strtok(NULL," "));	//retine greutatea
		int row = H/U-(H-height[i])/U;	//determina intervalul
		if(row >= 0 && row < H/U+1) {	//incrementeaza numarul de valori de pe interval
			nr_values[row]++;
		}
	}
	fclose(in);    //inchide fisierul
}

//calculeaza valorile dorite (greutatea maxima a gutuilor culese)
void calculeaza()
{
	int row,j,k;
	
	//pentru fiecare interval
	for(row=0;row<H/U+1;row++) {
		values[row] = (int*)malloc(sizeof(int)*(nr_values[row]+1));	//aloca memorie pentru valorile din interval
		nr_values[row] = 0;	//initializeaza numarul de valori din interval
	}
	
	for(j=0;j<N;j++) {	//pentru fiecare valoare
		int row = H/U-(H-height[j])/U;	//determina intervalul
		if(row >= 0 && row < H/U+1) {	//adauga valoarea la interval
			values[row][nr_values[row]++] = j;
		}
	}
	
	for(row=0;row < H/U+1;row++) {	//pentru fiecare interval
		int nr = nr_values[row];	//retine numarul de valori din interval
		//sorteaza intervalul
		for(j=0;j<nr-1;j++) {
			for(k=j+1;k<nr;k++) {
				//daca elementele trebuie interschimbate (comparatorul fiind greutatea)
				if(weight[values[row][j]] < weight[values[row][k]]) {
					int aux = values[row][j];
					values[row][j] = values[row][k];
					values[row][k] = aux;
				}
			}
		}
	}
	//pentru fiecare nivel, elimina elementele in plus (pastreaza doar valorile ce ar putea fi folosite)
	for(row=0;row < H/U+1;row++) {
		nr_values[row] = min(nr_values[row],H/U-row+1);
	}
	
	//pentru fiecare interval
	for(row=H/U;row>0;row--) {
		int nr1 = nr_values[row];	//numarul de valori din intervalul row
		int nr2 = nr_values[row-1];	//numarul de valori din intervalul row-1
		int size = H/U-row + 2;		//marimea maxima a interclasarii intervalelor
		int* new_values = (int*)malloc(sizeof(int)*size);	//aloca memorie pentru vector
		int p1 = 0,p2 = 0,p = 0;	//pozitia in row, row2 si in interclasare
		
		//pentru fiecare element
		for(j=0;j<min(nr1+nr2,size);j++) {
			if(p1 == nr1) {	//daca nu mai sunt in primul vector
				if(p2 != nr2) {	//daca mai sunt in al doilea
					new_values[p++] = values[row-1][p2++];	//retine valoarea din al doilea vector
				} else {
					break;
				}
			} else {
				if(p2 == nr2) {	//daca nu mai sunt elemente in al doilea vector
					new_values[p++] = values[row][p1++];	//retine valoarea din primul vector
				} else { //daca exista ambele valori
					if(weight[values[row][p1]] < weight[values[row-1][p2]]) { //daca valoarea din al doilea vector e mai mare
						new_values[p++] = values[row-1][p2++]; //retine valoarea din al doilea vector
					} else {
						new_values[p++] = values[row][p1++];	//retine valoarea din primul vector
					}
				}
			}
		}
		//daca trebuie alocate mai multe pozitii in intervalul curent
		if(p > nr_values[row-1]) {
			free(values[row-1]);	//elibereaza alocarea curenta
			values[row-1] = malloc(sizeof(int)*(p+1));	//aloca memoria noua
		}
		nr_values[row-1] = p;	//retine numarul nou de valori
		for(j=0;j<p;j++) {		//retine fiecare valoare
			values[row-1][j] = new_values[j];
		}
		//elibereaza memoria folosita
		free(new_values);
		free(values[row]);
	}
	
	//adauga fiecare valoare din ultimul interval
	for(j=0;j<nr_values[0];j++) {
		greutate_max += weight[values[0][j]];
	}
}

//scrie rezultatele in fisierul de iesire
void scrie(char* nume_fisier)
{
	FILE* out = fopen(nume_fisier,"w");    //deschide fisier
	fprintf(out,"%i",greutate_max);		   //scrie greutatea maxima
	fclose(out);   //inchide fisier
}

int main(int argc,char** argv)
{
	citeste("gutui.in");  //citeste matricea din fisier
	calculeaza();      //calculeaza valorile dorite
	scrie("gutui.out");    //scrie rezultatele in fisier
	return 0;
}