//VASILACHE RAZVAN ANDREI 335 CB TEMA 1 PA PROB 2 - "GUTUI"
#include <stdio.h>
#include <stdlib.h>
#define MAX 100001

//n,h,u - le citim din fisierul de intrare. g_out - greutatea maxima a gutuilor pe care le poate culege
//suma elementelor din v_rez reprezinta greutatea ceruta. 
//ind_v_rez este indicele acestui vector, care se actualizeaza cand gasesc o solutie valida
//"aux" este un vector auxiliar, si il folosim in functia "afla_g_out"
unsigned int n,h,u,g_out=0,v_rez[MAX],ind_v_rez=0;  
unsigned int aux[MAX];

//folosim structura "gut", gut[i] retinand inaltimea si greutatea gutuii "i"
struct gutuie {
       unsigned int inaltime,greutate;
       };
struct gutuie * gut;


//functie cu ajutorul careia folosim qsort pt a sorta descrescator vectorul de gutui dupa inaltime
int functie_qsort(const void* a,const void* b) {
    gutuie x,y;
    x=*((gutuie*)a);
    y=*((gutuie*)b);
    if(x.inaltime>y.inaltime) return -1;
    else return 1; 
}

//functie cu ajutorul careia calculam g_out - greutatea maxima pe care o poate culege gigel    
void afla_g_out() {
     unsigned int ind_aux=0,minim,i,j;
     
     for(i=0;i<n;i++) 
       if(gut[i].inaltime <= h) {                       //daca inaltimea ii permite, culege si scade "h" cu "u" 
         v_rez[ind_v_rez++]=gut[i].greutate;            
         aux[ind_aux++]=gut[i].greutate;                //in "aux" retinem greutatile culese 
		 if(h<u) h=0;
         else h=h-u; 
		 }
       else {
         minim=0;
		 for (j=1;j<ind_aux;j++) {				                     //altfel aflam indicele greutatatii minime din "aux" in "minim"
		   if (aux[j]<aux[minim]) 
		     minim=j;
			 }			
	     if (gut[i].greutate>aux[minim]) { 	                         //daca cumva greutatea curenta e mai mare decat cea dp "min" 			
		   v_rez[ind_v_rez++]=gut[i].greutate - aux[minim];          //adica am pierdut o solutie
    	   aux[minim]=gut[i].greutate;                               //punem in vectorul de solutii greutatea corecta - cea gresita 
		   }                                                         //astfel incat adunate sa dea cea corecta
       }
     
     for(i=0;i<=ind_v_rez;i++)                                       //adunam toate elementele lui "v_rez" si dam peste G maxim 
       g_out=g_out+v_rez[i];     		
     }         

int main() {
    unsigned int i;
    FILE * fis1;
    fis1=fopen("gutui.in","r");
    
    FILE * fis2;
    fis2=fopen("gutui.out","w");
    
    //citim numarul de gutui(n), inaltimea maxima la care ajunge gigel(h) si cu cat se ridica copacul(u)
    fscanf(fis1,"%i %i %i\n",&n,&h,&u);
    
    //alocam memorie pentru "gut"
    gut=(struct gutuie*)malloc(n*sizeof(struct gutuie));
    
    //citim pentru fiecare gutuie inaltimea si greutatea sa    
    for(i=0;i<n;i++)
      fscanf(fis1,"%i %i\n",&gut[i].inaltime,&gut[i].greutate);
    
    //sortam descrescator vectorul de gutui dupa inaltime     
    qsort(gut,n,sizeof(gutuie),functie_qsort);
    
    //calculam greutatea ceruta
    afla_g_out();
    
    //apoi o afisam in fisierul de iesire
    fprintf(fis2,"%i",g_out);
    return 0;
    }