#include <stdio.h>
#include <stdlib.h>
long int *height, *kg, *lvl, *nr, collected = 0, forbidden = 0, sum = 0; //collected va retine numarul de gutui culese intrun anumit moment, forbidden numarul de gutui innacesibile
long int aux = 0, aux2 = 0, i_aux = -1;
unsigned char *bad;
void quickSort (long int v[], long int a[], long int b[], long int lo, long int hi){ //functiea de sortare, v este vectorul principal dupa care se efectuaza sortarea
long int i, j, aux;
long int x;
i = lo;
j = hi;
x = v[(lo+hi)/2];
do
{
while (v[i]>x) i++;
while (v[j]<x) j--;
if (i<=j){
aux = v[i]; v[i] = v[j]; v[j] = aux;
aux = a[i]; a[i] = a[j]; a[j] = aux;
aux = b[i]; b[i] = b[j]; b[j] = aux;
i++; j--;
}
}while (i<=j);
if (lo<j) quickSort(v, a, b, lo, j);
if (i<hi) quickSort(v, a, b, i, hi);
}
long int count(long int v[], long int k, long int N){ //numara cate gutui de aceeasi greutate sunt intre indicii k si N-1
int i, nr = 2;
i = k;
do{
if(v[k] == v[++i]){
nr++;
}
else return nr;
}while(i<N);
return nr;
}
long int count_lvl(long int v[], long int l[], long int k, long int N){ //numara cate gutui de aceeasi greutate se afla la acelasi nivel intre indicii k si N-1
int i, nr = 2;
i = k;
do{
i++;
if(v[k] == v[i] && l[k] == l[i]){
nr++;
}
else return nr;
}while(i<N);
return nr;
}
void take(long int i){ //functie care face "culegerea" unei gutui i
sum = sum + kg[i];
//printf("ia i = %ld, -> height = %ld, kg = %ld, lvl = %ld, nr = %ld\n", i, height[i], kg[i], lvl[i], nr[i]);
forbidden++;
lvl[i] = -1;
bad[i] = 1;
collected++;
}
int main(){
long int i, j, k, num, current, start, end, to_take, N, H, U;
FILE *fp_in, *fp_out;
fp_in = fopen("gutui.in", "r");
fscanf(fp_in, "%ld %ld %ld\n", &N, &H, &U);
height = malloc(N*sizeof(long int));
kg = malloc(N*sizeof(long int));
lvl = malloc(N*sizeof(long int));
nr = malloc(N*sizeof(long int));
bad = malloc(N*sizeof(unsigned char));
for(i=0 ; i<N ; i++){
fscanf(fp_in, "%ld %ld\n", &height[i], &kg[i]);
if(height[i] > H){
lvl[i] = -1;
forbidden++;
bad[i] = 1;
}
else{
lvl[i] = (H - height[i])/U;
bad[i] = 0;
}
nr[i] = 1;
}
fclose(fp_in);
quickSort(kg, height, lvl, 0, N-1); //se sorteaza vectorul dupa greutate descrescator
i = 0;
while(i<(N-1)){ //se sorteaza inaltimile pentru fiecare greutate fara a tine cont de lvl
if(kg[i] == kg[i+1]){
k = i;
num = count(kg, (k+1), N);
i = k + num;
quickSort(height, kg, lvl, k, i-1);
}
else i++;
}
i = 0;
while(i<(N-1)){ //se numara gutuile care au aceasi greutate si se afla la acelasi lvl
if(kg[i] == kg[i+1] && lvl[i] == lvl[i+1]){
k = i;
num = count_lvl(kg, lvl, (k+1), N);
i = k + num;
for(j=k ; j<i ; j++){
nr[j] = num;
}
}
else i++;
}
start = 0; end = N;
i = start;
to_take = start;
do{
if(aux < (nr[i]-1) && bad[i] == 0){
i_aux = i + 1;
aux2 = aux + nr[i] - 1;
}
if(i == i_aux){
aux = aux2;
}
current = lvl[i] - collected - aux;
// printf("i = %ld -> current = %ld :: aux = %ld\n", i, current, aux);
if(current >= 0){
if(current == (nr[i] - 1)){
for(j=(i+nr[i]-1) ; j>=i ; j--){
take(j);
if(j == end-1){
end--;
}
}
if(i == start){
start++;
}
i = start; aux = 0; aux2 = 0; i_aux = -1;
}
else if(current == 0){
take(i);
if(i == start){
start++;
}
if(i == end-1){
end--;
}
i = start; aux = 0; aux2 = 0; i_aux = -1;
}
else{
if(i == (end-1)){
if(to_take == start){
take(start);
start++;
to_take++;
i = start; aux = 0; aux2 = 0; i_aux = -1;
}
else {
i = start; aux = 0; aux2 = 0; i_aux = -1;
to_take = start;
}
}
else i++;
}
}
else{
if(i != (end-1)){
if(bad[i] == 0){
bad[i] = 1;
forbidden++;
}
i++;
}
else {
if(bad[i] == 0){
bad[i] = 1;
forbidden++;
}
if(to_take == start){
take(start);
start++;
to_take++;
i = start; aux = 0; aux2 = 0; i_aux = -1;
}
else {
i = start; aux = 0; aux2 = 0; i_aux = -1;
to_take = start;
}
}
}
}while(forbidden < N);
fp_out = fopen("gutui.out", "w");
fprintf(fp_out, "%ld\n", sum);
fclose(fp_out);
return 0;
}