#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <unistd.h>
int suma=0;
void sortare(int n,int *hgutuie,int *ggutuie){//sortez descresc dupa h
int aux1,aux2,i,j;
for (i=0;i<n-1;i++)
for (j=i+1;j<n;j++)
if (hgutuie[i]<hgutuie[j]){
aux1=hgutuie[i];
hgutuie[i]=hgutuie[j];
hgutuie[j]=aux1;
aux2=ggutuie[i];
ggutuie[i]=ggutuie[j];
ggutuie[j]=aux2;
}
}
int max(int i, int n, int hmax, int u, int *hgutuie, int *ggutuie){
int j=0,max=ggutuie[i];
for (j=i;i<n;i++)
if ((hmax-hgutuie[j])<=u)
if(ggutuie[j]>=max)
max=ggutuie[j];
return max;
}
int next(int j, int n, int hmax,int u, int *hgutuie, int *ggutuie){
int i,gasit;
for (i=j;i<n;i++)
if ((hmax-hgutuie[i])>u)
return i;
}
/*int rezolvare(int i, int n,int hmax,int u, int *hgutuie, int *ggutuie){
//int i=0;
//for (i=0;i<n;i++){
// if ((hmax-hgutuie[i])<0) break;//nu va intra niciodata in caz
if (hmax>0){
if (((hmax-hgutuie[i])<=u)&&(hmax-hgutuie[i]>=0)&&(i<n)){//daca ma aflu in cel mai mare interval de inaltimi
suma+=max(i,n,hmax,u,hgutuie,ggutuie);//adun la suma maximul greutatilor din acel interval;
//printf("%d",max);
//return -1;
// i=next(i,n,hmax,u,hgutuie,ggutuie);//ma duc cu indicele pe primul hgutuie care nu este in ult terminal;
i++;
hmax=hmax-u;
}
if (hmax-hgutuie[i]<=0){
//i++;
rezolvare(i,n,hmax+u,u,hgutuie,ggutuie);
}
if ((hmax-hgutuie[i]==u))
rezolvare(i,n,hmax,u,hgutuie,ggutuie);
if ((hmax-hgutuie[i])>u)//daca nu ma aflu in ultimul interval
rezolvare(i,n,hmax-u,u,hgutuie,ggutuie);
}
return suma;
}*/
/*int rezolvare(int i, int n,int hmax,int u, int *hgutuie, int *ggutuie){
if ((hmax>0)&&(i<n)) { //daca am pas inaltime si indicele nu depaseste n
if ((hgutuie[i]<=hmax)&&(hgutuie[i]>=hmax-u)) { //daca ma aflu in ultimul interval
suma+=max(i,n,hmax,u,hgutuie,ggutuie); //adun la suma maximul din acel interval
i++;//ma duc pe urmatorul elem din vectorul sortat pe inaltimi
if (hgutuie[i]<0) return suma;
hmax=hmax-u;//scad inaltimea maxima
//if ((hgutuie[i]<=hmax+u)&&(hgutuie[i]>=hmax)&&(i<n)&&(i<n)) //daca si urmatorul e in intervalul celui precedent
// if (hmax-hgutuie[i]<u){
// i++;//verific inaltimea pt urmatorul
// rezolvare(i,n,hmax,u,hgutuie,ggutuie);//daca inaltimea nu e buna ma duc pe urmatorul element
// }
//daca inaltimea este buna, repet functia, dar cu inaltimea maxima - u
if (hgutuie[i]>0)//daca nu depasesc vectorul
rezolvare(i,n,hmax,u,hgutuie,ggutuie);//fac recursiv
}
//daca nu ma aflu in ultimul interval
//daca hgutuie e mai mare decat hmax
if ((hgutuie[i]>hmax)&&(hgutuie[i]>0)){
i++;
rezolvare(i,n,hmax,u,hgutuie,ggutuie);
}//trec pe urmatorul element
if (hgutuie[i]>0){//daca nu e mai mare decat max, e mai mic decat partea inferioara a intervalului
hmax=hmax-u;//scad din inaltime
rezolvare(i,n,hmax,u,hgutuie,ggutuie);//repet, dar cu inaltimea micsorata;
}
}
if ((hgutuie[i]<0)||(i>=n)||(hmax<=0))
return suma;
}*/
int rezolvare(int i, int n, int hmax, int u, int *hgutuie, int *ggutuie){
while ((hmax>0)&&(i<n)&&(hgutuie[i]>0)){
//daca ma aflu in ultimul interval;
if ((hgutuie[i]<=hmax)&&(hgutuie[i]>=hmax-u)){
hmax=hmax-u;//scad inaltimea maxima
suma+=max(i,n,hmax,u,hgutuie,ggutuie);//adun la suma maximul elementelor din acel interval de la acel indice inainte
i++;
}
//daca e mai mare decat limita superioara
if (hgutuie[i]>hmax)
i++;
//daca e mai mic decat limita inferioara
if (hgutuie[i]<hmax-u)
hmax=hmax-u;//scad din inaltimea maxima;
if ((hgutuie[i]<=hmax)&&(hgutuie[i]>=hmax-u)){
if (hmax-hgutuie[i]!=u)
hmax=hmax-u;//scad inaltimea maxima
suma+=max(i,n,hmax,u,hgutuie,ggutuie);//adun la suma maximul elementelor din acel interval de la acel indice inainte
}
i++;
}
return suma;
}
int main(){
FILE *fin=fopen("gutui2.in","r");
FILE *fout=fopen("gutui.out", "w");
int n,h,u;
fscanf(fin, "%d %d %d",&n,&h,&u);
//verific date intrare prima linie corecte
//printf("numarul de gutui este: %d\ninaltimea maxima este: %d\ninaltime gutuie este: %d\n",n,h,u);
int i=0;
int *hgutuie=malloc(n*sizeof(int));//aloc dinamic vect de inalt gutui
int *ggutuie=malloc(n*sizeof(int));//si de greutate gutui
for (i=0;i<n;i++)
fscanf(fin, "%d %d",&hgutuie[i],&ggutuie[i]);//pun in 2 vectori inaltime si greut coresp gutuie
// for(i=0;i<n;i++)
// printf("inaltime:%d, greutate:%d\n",hgutuie[i],ggutuie[i]);//verific vectorii;
sortare(n,hgutuie,ggutuie);
//for(i=0;i<n;i++)
// printf("inaltime:%d, greutate:%d\n",hgutuie[i],ggutuie[i]);//verific vectorii;
//printf("%d", rezolvare(0,n,h,u,hgutuie,ggutuie));
//getch();
int rasp=rezolvare(0,n,h,u,hgutuie,ggutuie);
fprintf(fout,"%d",rasp);
fclose(fin);
fclose(fout);
return 0;
}