/*
Gigel are in curte un gutui. El se hotaraste sa culeaga cat mai multe gutui, dar are o problema: copacul este atat de incarcat 
* cu fructe incat la fiecare gutuie culeasa, toate crengile acestuia se ridica in inaltime cu fix U centimetrii. Din pacate Gigel 
* nu are scara la el si nu poate sa culeaga gutui la o inaltime mai mare de H centimetrii.

Nici de aceasta data Gigel nu se descurca singur. Ajutati-l sa culeaga cat mai multe gutui.

Stiind greutatea si inaltimea initiala a fiecarui fruct, se cere cea mai mare recolta de gutui pe care o poate aduce Gigel acasa.
*  Cum se gandeste sa le vanda in piata, il intereseaza o greutate cat mai mare, nu un numar cat mai mare.

Date de intrare
Pe prima linie a fisierului de intrare gutui.in se afla 3 numere intregi: N (numarul de gutui din copac), H (inaltimea maxima la 
* care ajunge Gigel) si U (cu cat se ridica crengile copacului dupa culegerea unei gutui).
Pe urmatoarele N linii se afla cate 2 numere intregi reprezentand inaltimiile si greutatile gutuilor din copac.

Date de ieşire
In fisierul de iesire gutui.out trebuie scrisa greutatea maxima a gutuilor pe care le poate culege Gigel.
*/
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <stdio.h>

struct gutui
{
	long int inaltime;
	long int greutate;
	
};
typedef struct gutui Gutui;
struct date
{
	Gutui fruct; 		/**< file-descriptorul */
	long int priority;		/**< timpul ramas */
};
typedef struct date date_t;
void quicksort(date_t * arr, long int low, long int high) {
 long int i = low;
 long int j = high;
 date_t y ;
 /* compare value */
 date_t z = arr[(low + high) / 2];

 /* partition */
 do {
  /* find member above ... */
  while(arr[i].priority < z.priority) i++;

  /* find element below ... */
  while(arr[j].priority > z.priority) j--;

  if(i <= j) {
   /* swap two elements */
   y = arr[i];
   arr[i] = arr[j]; 
   arr[j] = y;
   i++; 
   j--;
  }
 } while(i <= j);

 /* recurse */
 if(low < j) 
  quicksort(arr, low, j);

 if(i < high) 
  quicksort(arr, i, high); 
}

int main()
{
	FILE *pf_int,*pf_ies;
	long int x,j=0, k=0,n_aux=0,n_cules=0,i = 0 , N = 0 , kg=0 , posibil=0, H = 0 , U = 0 ;
	date_t *copac,*aux,*cules;
	date_t data,data2;
	Gutui gutuie;
	pf_int = fopen("gutui.in","r");
	pf_ies = fopen("gutui.out","w");
	fscanf(pf_int,"%ld %ld %ld",&N,&H,&U);
	copac=(date_t*)malloc((N+1)*sizeof(date_t));
	cules=(date_t*)malloc((N+1)*sizeof(date_t));
	for( i = 0; i < N ; i++ )
	{
		fscanf(pf_int,"%ld %ld",&data.fruct.inaltime,&data.fruct.greutate);
		data.priority=data.fruct.inaltime;
		copac[i]=data;
		printf("%ld\n",copac[i].priority);
	}
	printf("am iesit %ld \n",N);
	quicksort(copac,0,N-1);
	printf("am iesit %ld \n",N);
	i=N-1;
	while((i>0)&&(copac[i].fruct.inaltime > H))
	{
		i--;//ajung la prima gutuie care poate  fi culeasa
	}
	
	if(i>0)
	{
		posibil=((H-copac[i].fruct.inaltime)/U);
		H=H-posibil*U;
	}
	for(x = 0 ; x < N; x++ )
	{
		printf("copac cu fructe %ld %ld %ld\n",x,copac[x].fruct.inaltime,copac[x].fruct.greutate);
	//	kg+=cules.vec[i].fruct.greutate;
	}
		
	aux=(date_t*)malloc((N+1)*sizeof(date_t));
	printf("am iesit %ld \n",N);
	while(i>=0)
	{
		memset(aux,0,(N+1)*sizeof(date_t));
		posibil++;
		//cat timp sunt intr-o treapta pe care pot sa culeg
		data2=copac[i];//extrag un fruct de la inaltimea maxima,daca e pe o ramura
		printf("= %ld %ld\n",data2.fruct.inaltime,data2.fruct.greutate);
		n_aux=0;
		while((data2.fruct.inaltime > ( H - U ) )&&(i>=0))
		{
			data=copac[i];
			printf("%ld %ld %ld\n",i,data.fruct.inaltime,data.fruct.greutate);
			data.priority=data.fruct.greutate;		
			aux[n_aux]=data;
			n_aux++;
			i--;
			data2=copac[i];
			
		}
		printf("posibil %ld\n",posibil);
		//contor=0;
		if(n_aux>0)
		{
			printf("1 posibil %ld\n",posibil);
			if(n_aux>1)
				quicksort(aux,0,n_aux-1);

			while((posibil>0)&&(n_aux>0))//cate gutuie ar putea fi culese de pe pozitia respectiva
			{
				printf("2 posibil %ld\n",posibil);
				data=aux[n_aux-1];
				n_aux--;
				cules[n_cules]=data;//introduc in cos
				posibil--;
				n_cules++;
			}
			/*if(n_cules>1)
			{
				printf("3 posibil %ld\n",posibil);
				if(n_cules>1)
				quicksort(cules,0,n_cules-1);
			}*/
			if(n_aux>0)
			{
				printf("4 posibil %ld\n",posibil);
				data=aux[n_aux-1];
				j=0;
				while((cules[j].priority<data.priority)&&(j<n_cules)&&(n_aux>0))//cat timp in trecut am cules un fruct mai usor
				{
					printf("5 posibil %ld\n",posibil);
					cules[j]=data;
					j++;
					n_aux--;
					data=aux[n_aux-1];
				}
			
					
					printf("6 posibil %ld\n",posibil);
					
				
			}
			if(n_cules>1)
			quicksort(cules,0,n_cules-1);
			
		}
		printf("7 posibil %ld\n",i);
		H=H-U;
		//free(&aux);
	}
	for(i = 0 ; i < n_cules; i++ )
	{
		printf("%ld %ld %ld\n",i,cules[i].fruct.inaltime,cules[i].fruct.greutate);
		kg+=cules[i].fruct.greutate;
	}
	fprintf(pf_ies,"%ld\n",kg);
	fclose(pf_int);
	fclose(pf_ies);
	return 0;
}