#include<stdio.h>
#include<stdlib.h>
typedef struct{
int h, g, niv;
}gutui;
typedef struct{
int g, niv;
}vector;
typedef struct{
int *g, niv, elem;
}vector1;
void quickSort1(gutui *vect, int stanga, int dreapta) {
int i = stanga, j = dreapta;
int tmp1, tmp2, tmp3;
int pivot = vect[dreapta].niv;
while (i <= j){
while (vect[i].niv < pivot)
i++;
while (vect[j].niv > pivot)
j--;
if (i <= j){
tmp1=vect[i].niv;
vect[i].niv=vect[j].niv;
vect[j].niv=tmp1;
tmp2=vect[i].h;
vect[i].h=vect[j].h;
vect[j].h=tmp2;
tmp3=vect[i].g;
vect[i].g=vect[j].g;
vect[j].g=tmp3;
i++;
j--;
}
}
if (stanga < j)
quickSort1(vect, stanga, j);
if (i < dreapta)
quickSort1(vect, i, dreapta);
}
void quickSort2(gutui *vect, int stanga, int dreapta) {
int i = stanga, j = dreapta;
int tmp1, tmp2, tmp3;
int pivot = vect[dreapta].g;
while (i <= j){
while (vect[i].g > pivot)
i++;
while (vect[j].g < pivot)
j--;
if (i <= j){
tmp1=vect[i].niv;
vect[i].niv=vect[j].niv;
vect[j].niv=tmp1;
tmp2=vect[i].h;
vect[i].h=vect[j].h;
vect[j].h=tmp2;
tmp3=vect[i].g;
vect[i].g=vect[j].g;
vect[j].g=tmp3;
i++;
j--;
}
}
if (stanga < j)
quickSort2(vect, stanga, j);
if (i < dreapta)
quickSort2(vect, i, dreapta);
}
int main(){
int n, h, u, i, j, k, nivele, dif=1, suma=0, max, t;
gutui *gut;
vector *vec;
vector1 *list;
FILE *fo, *fc;
fo=fopen("gutui.in", "r");
fscanf(fo,"%d%d%d", &n, &h, &u);
gut=(gutui*)malloc(n*sizeof(gutui));
nivele=h/u;
for(i=0;i<n;i++){
fscanf(fo,"%d%d", &gut[i].h, &gut[i].g);
gut[i].niv=nivele-gut[i].h/u;
}
fclose(fo);
/*
for(i=0;i<n;i++)
printf("%d\t", gut[i].g);
printf("\n");
for(i=0;i<n;i++)
printf("%d\t", gut[i].h);
printf("\n");
for(i=0;i<n;i++)
printf("%d\t", gut[i].niv);
printf("\n");
printf("\n");
*/
quickSort1(gut,0,n-1);
i=0;
for(j=0;j<n;j++){
if(gut[i].niv!=gut[j].niv){
//if(j==n-1)
// quickSort2(gut,i,j);
//else
quickSort2(gut,i,j-1);
i=j;
}
}
for(i=0;i<n-1;i++)
if(gut[i].niv!=gut[i+1].niv)
dif++;
vec=(vector*)calloc((dif+n),sizeof(vector));
j=0;
k=1;
i=0;
vec[0].niv=gut[0].niv;
while(i<n){
if(vec[j].niv!=vec[j].g){
if(gut[i].niv==vec[j].niv){
vec[j].g++;
vec[k].g=gut[i].g;
vec[k].niv=gut[i].niv;
k++;
}
else{
j=k;
vec[j].niv=gut[i].niv;
vec[j].g++;
k++;
vec[k].g=gut[i].g;
vec[k].niv=gut[i].niv;
k++;
}
i++;
}
else{
while(gut[i].niv==vec[j].niv)
i++;
j=k;
vec[j].niv=gut[i].niv;
vec[j].g++;
k++;
vec[k].g=gut[i].g;
vec[k].niv=gut[i].niv;
k++;
i++;
}
}
list=(vector1*)malloc(dif*sizeof(vector1));
i=0;
k=0;
for(k=0;k<dif;k++){
list[k].niv=vec[i].niv;
list[k].elem=vec[i].g;
list[k].g=(int*)calloc(vec[i].g,sizeof(int));
for(j=0;j<vec[i].g;j++)
list[k].g[j]=vec[i+j+1].g;
i=i+vec[i].g+1;
}
//construire solutie
j=0;
while(j<dif){
t=j;
max=list[j].g[0];
for(i=j+1;i<dif-1;i++){
if(list[i].niv-list[j].niv<=list[i].elem)
if(max<list[i].g[list[i].niv-list[j].niv]){
max=list[i].g[list[i].niv-list[j].niv];
t=i;
}
}
suma=suma+max;
for(k=list[t].niv-list[j].niv;k<list[t].elem-1;k++)
list[t].g[k]=list[t].g[k+1];
for(k=0;k<dif;k++){
if(list[k].elem==list[k].niv)
list[k].elem-=1;
list[k].niv-=1;
}
if(list[j].niv==0)
j++;
}
/*
for(i=0;i<n;i++)
printf("%d\t", gut[i].g);
printf("\n");
for(i=0;i<n;i++)
printf("%d\t", gut[i].h);
printf("\n");
for(i=0;i<n;i++)
printf("%d\t", gut[i].niv);
printf("\n");
printf("\n");
for(i=0;i<n+dif;i++)
printf("%d\t", vec[i].g);
printf("\n");
for(i=0;i<n+dif;i++)
printf("%d\t", vec[i].niv);
printf("\n\n");
for(i=0;i<dif;i++){
for(j=0;j<list[i].elem;j++)
printf("%d ", list[i].g[j]);
printf("\n");
}
printf("suma este = %d", suma);
*/
free(gut);
free(vec);
for(k=0;k<dif;k++)
free(list[k].g);
free(list);
fc=fopen("gutui.out", "w");
fprintf(fc,"%d\n",suma);
fclose(fc);
return 0;
}