#include <stdio.h>
#include <stdlib.h>
#define true 1
#define false 0
typedef struct Node{
int h,w;
struct Node *next;
} node;
typedef node* linkedList;
node* newNode (int h, int w, node *nextNode){
node *aNode = (node*)malloc(sizeof(node));
aNode -> h = h;
aNode -> w = w;
aNode -> next = nextNode;
return aNode;
}
void setNext(node *aNode, node* nextNode){
aNode -> next = nextNode;
}
int listInsert(linkedList aList, int maxEl, node *aNode) {
node * tempNode = aList;
int listCount = 0;
while (tempNode -> next != NULL && tempNode -> next -> w > aNode -> w && listCount < maxEl) {
tempNode = tempNode -> next;
listCount ++;
}
if (listCount == maxEl)
return false;
setNext(aNode,tempNode->next);
setNext(tempNode,aNode);
return true;
}
int isEmpty(linkedList aList){
if (aList -> next == NULL)
return true;
return false;
}
node *getNextNode(linkedList aList){
node * tempNode = aList -> next;
aList -> next = aList -> next -> next;
return tempNode;
}
int main() {
FILE *fin, *fout;
int N, H, U;
fin = fopen("gutui.in","r");
fout = fopen("gutui.out","w");
fscanf(fin,"%d %d %d", &N, &H, &U);
//printf("%d %d %d\n",N,H,U);
int i;
// Make list of lists
int noOfLists = H/U;
if (H/U) noOfLists++;
linkedList *lists = (linkedList*) malloc (noOfLists * sizeof(linkedList));
//linkedList lists[100];
for (i = 0 ; i < noOfLists ; i++) {
lists[i] = (linkedList) malloc(sizeof(node));
}
//listInsert(lists[0],N,newNode(4,10,NULL));
//printf("%d %d\n",lists[0] -> next -> w, lists[0] -> next -> h);
// Read elements and fill the lists
for (i = 0 ; i < N ; i++) {
int h, w, listNo;
fscanf(fin,"%d %d",&h, &w);
listNo = (H - h)/U;
//printf("%d %d %d\n",h,w,listNo);
listInsert(lists[listNo],N,newNode(h,w,NULL));
}
/*
// print lists
for (i = 0 ; i < noOfLists ; i++) {
printf("lista %d:\n",i);
while (isEmpty(lists[i]) == false) {
node * tempNode = getNextNode(lists[i]);
int h = tempNode -> h;
int w = tempNode -> w;
printf ("%d %d\n",h, w);
}
printf("\n");
}*/
linkedList selected = (linkedList) malloc (sizeof(node));
for (i = 0 ; i < noOfLists ; i++) {
int inserted = true;
while (isEmpty(lists[i]) == false && inserted == true) {
inserted = listInsert(selected,i + 1,getNextNode(lists[i]));
}
}
unsigned long long suma = 0;
while (isEmpty(selected) == false)
suma += getNextNode(selected) -> w;
fprintf(fout,"%lld",suma);
fclose(fin);
fclose(fout);
return 0;
}