#include <stdio.h>
#include <stdlib.h>
struct gut{
unsigned int level;
unsigned int weight;
};
struct gut *gutui;
int compare (const void * a, const void * b)
{
if ((*(struct gut*)a).level == (*(struct gut*)b).level)
return -((*(struct gut*)a).weight - (*(struct gut*)b).weight);
return ((*(struct gut*)a).level - (*(struct gut*)b).level);
}
unsigned int parent(unsigned int i){
if (i % 2 == 0) return (i/2 - 1);
else return i/2;
}
void insert(unsigned int w, unsigned int *heap, unsigned int pos){
heap[pos] = w;
unsigned int aux;
while ((pos > 0) && (heap[pos] < heap[parent(pos)])) {
aux = heap[parent(pos)];
heap[parent(pos)] = heap[pos];
heap[pos] = aux;
pos = parent(pos);
}
}
void minheapify(unsigned int *heap, unsigned int i, unsigned int length){
unsigned int l = 0, r = 0, least, aux;
if ((2 * i + 1) < length) l = 2 * i + 1;
if ((2 * i + 2) < length) r = 2 * i + 2;
if ((l == 0) || (r == 0)) return;
else
if ((l != 0) && (r == 0))
{
if (heap[l] < heap[i]) {
aux = heap[i];
heap[i] = heap[l];
heap[l] = aux;
minheapify(heap, l, length);
}
else return;
}
else
{
if (heap[l] > heap[r]) least = r;
else least = l;
if (heap[i] > heap[least]) {
//printf("!\n");
aux = heap[i];
heap[i] = heap[least];
heap[least] = aux;
minheapify(heap, least, length);
}
else return;
} }
int main(){
unsigned int i, j, k, t;
unsigned int h,u,n;
unsigned int level,no_levels, min_level = 0xffffffff;
unsigned int *schedule;
unsigned int max = 0;
FILE *f = fopen("gutui.in","r");
fscanf(f, "%u", &n);
fscanf(f, "%u", &h);
fscanf(f, "%u", &u);
/*
printf("n = %u h = %u u = %u\n", n ,h,u);
printf("%u\n", h/u);
*/
gutui = (struct gut *)malloc(n * sizeof(struct gut));
for (i = 0; i < n; i++)
{
fscanf(f, "%u", &level);
fscanf(f, "%u", &gutui[i].weight);
gutui[i].level = (h - level)/u + 1 ;
if (min_level > level) min_level = level;
}
fclose(f);
qsort(gutui, n, sizeof(struct gut), compare);
/*for (i = 0; i < n; i++)
{
printf("%u ", gutui[i].weight);
printf("%u \n", gutui[i].level);
}
printf("\n");*/
no_levels = (h - min_level)/u + 1;
unsigned int * heap = (unsigned int *)calloc(no_levels,sizeof(unsigned int));
for (i = 0; i < no_levels; i++)
heap[i] = 0xffffffff;
level = 0; k = 0; j = 0, t = 0;
for (i = 0; i < n; i++){
if (gutui[i].level > level) {
level = gutui[i].level;
k = 1;
if (t < level) {
t = t + 1;
insert(gutui[i].weight, heap, level - 1);
max = max + gutui[i].weight;
}
else
{
if (heap[0] < gutui[i].weight) {
max = max - heap[0] + gutui[i].weight;
heap[0] = gutui[i].weight;
minheapify(heap, 0, level);
}
}
}
else
{
k = k + 1;
if (k <= gutui[i].level)
if (t < level) {
t = t + 1;
insert(gutui[i].weight, heap, level - 1);
max = max + gutui[i].weight;
}
else
{
if (heap[0] < gutui[i].weight) {
max = max - heap[0] + gutui[i].weight;
heap[0] = gutui[i].weight;
minheapify(heap, 0, level);
}
}
}
j++;
}
/*unsigned int * heap = (unsigned int *)calloc(9,sizeof(unsigned int));
insert(36 , heap, 0);
insert(100 , heap, 1);
insert( 17, heap, 2);
insert(25 , heap, 3);
insert(19 , heap, 4);
insert( 2, heap, 5);
insert(7 , heap, 6);
insert(3 , heap, 7);
insert(1 , heap, 8);
//insert( , heap, 0);
for (i = 0; i < 9;i++)
printf("%u ", heap[i]);
printf("\n");
heap[0] = 5;
minheapify(heap, 0, 9);*/
//for (i = 0; i < no_levels;i++)
// printf("%u ", heap[i]);
//printf("\n");
//printf("%u\n", max);
f = fopen("gutui.out", "w");
fprintf(f, "%u\n", max);
fclose(f);
return 0;
}