#include <stdio.h>
#include <malloc.h>
#define u_int unsigned int
void merge(u_int **a, int low, int high, int mid){
int i, j, k;
u_int **c;
c = (u_int**)malloc((high+1)*sizeof(u_int*));
for(i = 0; i < high+1; i ++)
c[i] = (u_int*)malloc(2*sizeof(u_int));
i = low;
j = mid+1;
k = low;
while((i <= mid) && (j <= high)){
if(a[i][0] > a[j][0]){
c[k][0] = a[i][0];
c[k][1] = a[i][1];
i ++;
}
else{
c[k][0] = a[j][0];
c[k][1] = a[j][1];
j ++;
}
k ++;
}
while(i <= mid){
c[k][0] = a[i][0];
c[k][1] = a[i][1];
k ++;
i ++;
}
while(j <= high){
c[k][0] = a[j][0];
c[k][1] = a[j][1];
k ++;
j ++;
}
for(i = low; i < k; i ++){
a[i][0] = c[i][0];
a[i][1] = c[i][1];
}
for(i = 0; i < high+1; i ++)
free(c[i]);
free(c);
return;
}
void merge_sort(u_int **a, int low, int high){
int mid;
if(low<high){
mid = (low+high)/2;
merge_sort(a, low, mid);
merge_sort(a, mid+1, high);
merge(a, low, high, mid);
}
return;
}
int main(){
FILE *f, *g;
f = fopen ("gutui.in", "r");
g = fopen ("gutui.out", "w");
u_int H, U, **a, cules = 0, *momentan, h_mom;
int N, i, j, l_mom = 0, k, n;
fscanf(f, "%d %u %u", &N, &H, &U);
n = N;
a = (u_int**)malloc(N*sizeof(u_int*));
momentan = (u_int*)malloc(N*sizeof(u_int*));
for(i = 0; i < N; i ++){
a[i] = (u_int*)malloc(2*sizeof(u_int));
fscanf(f, "%u %u", &a[i][0], &a[i][1]);
}
//merge_sort descrescator
merge_sort(a, 0, N-1);
/*for(i = 0; i < N; i ++)
fprintf(g, "%d %d\n", a[i][0], a[i][1]);
*/
//pornesc de la ultimul nivel
if(H%U == 0)
h_mom = U;
else
h_mom = H - ((H / U) * U);
//incep sa "culeg" gutui, pornind de la ultimul nivel
while((h_mom <= H) && (N > 0 || l_mom > 0)){
//printf("aici: %d\n", N);
if(l_mom > 0){
cules = cules + momentan[l_mom-1];
//fprintf(g, "cules: %d\n", momentan[l_mom-1]);
l_mom --;
h_mom = h_mom + U;
}
else
h_mom = h_mom + U;
while(N > 0){
//fprintf(g, "aici: %d\n", N);
if(a[N-1][0] > h_mom)
break;
if(l_mom == 0){
momentan[l_mom] = a[N-1][1];
//fprintf(g, "momentan: %d\n", momentan[l_mom]);
l_mom ++;
N --;
}
else{
k = 1;
for(i = 0; i < l_mom; i ++)
if(momentan[i] > a[N-1][1]){
for(j = l_mom; j > i; j --)
momentan[j] = momentan[j-1];
l_mom ++;
momentan[i] = a[N-1][1];
//fprintf(g, "momentan: %d\n", momentan[i]);
N --;
k = 0;
break;
}
if(k){
momentan[l_mom] = a[N-1][1];
//fprintf(g, "momentan: %d\n", momentan[l_mom]);
l_mom ++;
N --;
}
}
}
}
free(momentan);
for(i = 0; i < n; i ++)
free(a[i]);
free(a);
fprintf(g, "%u", cules);
return 0;
}