#include <stdio.h>
#include <stdlib.h>
#define true 1
#define false 0
typedef struct Node{
int h,w;
struct Node *next;
unsigned char noOfElements;
} node;
typedef node* linkedList;
typedef struct bNode{
int h,w;
struct bNode * left, * right;
} BNode;
typedef struct {
BNode *nodes;
unsigned char noOfNodes;
} BTree;
void merge(int *h, int *w, int s, int m, int d) {
int i = s;
int j = m + 1;
int k = 0;
int h2[100000];
int w2[100000];
while (i <= m && j <= d) {
if (w[i] < w[j]) {
h2[k] = h[i];
w2[k++] = w[i++];
}
else {
h2[k] = h[j];
w2[k++] = w[j++];
}
}
for (; i <= m ; i++){
h2[k] = h[i];
w2[k++] = w[i];
}
for (;j <= d ; j++){
h2[k] = h[j];
w2[k++] = w[j];
}
for (i = 0 ; i <= (d-s) ; i++){
w[i+s] = w2[i];
h[i+s] = h2[i];
}
}
void mSort(int *h, int *w, int s, int d) {
if (s < d) {
int m = (s+d)/2;
mSort(h,w,s,m);
mSort(h,w,m+1,d);
merge(h,w,s,m,d);
}
}
BNode *newBNode(int h, int w) {
BNode *aBNode = (BNode*)malloc(sizeof(BNode));
aBNode -> left = NULL;
aBNode -> right = NULL;
aBNode -> h = h;
aBNode -> w = w;
return aBNode;
}
void add(BTree *aBTree, BNode *aBNode) {
BNode *tempBNode = aBTree -> nodes;
while (tempBNode != NULL) { // nu este frunza;
if (tempBNode -> w > aBNode -> w) {
if (tempBNode -> left != NULL) {
tempBNode = tempBNode -> left;
}
else { // insert in left
tempBNode -> left = aBNode;
return;
}
}
else {
if (tempBNode -> right != NULL) {
tempBNode = tempBNode -> right;
}
else { // insert in right;
tempBNode -> right = aBNode;
return;
}
}
}
aBTree -> nodes = aBNode;
}
void delMin(BTree *aBTree){
BNode *tempBNode = aBTree -> nodes;
BNode *parentBNode = NULL;
while (tempBNode != NULL) {
if (tempBNode -> left != NULL) {
parentBNode = tempBNode;
tempBNode = tempBNode -> left;
}
else {
if (parentBNode != NULL) {
parentBNode -> left = tempBNode -> right;
return;
}
else {
aBTree -> nodes = tempBNode -> right;
return;
}
}
}
}
void printBTree(BNode *aBNode) {
if (aBNode != NULL) {
if (aBNode -> left != NULL)
printBTree (aBNode -> left);
printf("%d(%d) ",aBNode -> h, aBNode -> w);
if (aBNode -> right != NULL)
printBTree (aBNode -> right);
}
}
void countValues(BNode *aBNode, unsigned long long *suma) {
if (aBNode != NULL) {
if (aBNode -> left != NULL)
countValues (aBNode -> left, suma);
*suma += aBNode -> w;
//printf("%d(%d) ",aBNode -> h, aBNode -> w);
//printf("suma = %lld ", *suma);
if (aBNode -> right != NULL)
countValues (aBNode -> right, suma);
}
}
node* newNode (int h, int w, node *nextNode){
node *aNode = (node*)malloc(sizeof(node));
aNode -> h = h;
aNode -> w = w;
aNode -> next = nextNode;
aNode -> noOfElements = 0;
return aNode;
}
void setNext(node *aNode, node* nextNode){
aNode -> next = nextNode;
}
int listInsertAsc(linkedList aList, int maxEl, node *aNode) {
node * tempNode = aList;
while (tempNode -> next != NULL && tempNode -> next -> w < aNode -> w) {
tempNode = tempNode -> next;
}
setNext(aNode,tempNode->next);
setNext(tempNode,aNode);
return true;
}
int listInsertDesc(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;
}
void printList(linkedList aList) {
node * tempNode = aList -> next;
while (tempNode != NULL){
printf("%d %d\n",tempNode -> h, tempNode -> w);
tempNode = tempNode ->next;
}
}
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);
int i;
int *h = (int*)malloc(N*sizeof(int));
int *w = (int*)malloc(N*sizeof(int));
// Read elements
for (i = 0 ; i < N ; i++) {
fscanf(fin,"%d %d", &h[i], &w[i]);
}
// Sort elements
mSort(h,w,0,N-1);
// Make list of lists
int noOfLists = H/U;
if (H % U) noOfLists++;
linkedList *lists = (linkedList*) malloc (noOfLists * sizeof(linkedList));
for (i = 0 ; i < noOfLists ; i++) {
lists[i] = (linkedList) malloc(sizeof(node));
lists[i] -> noOfElements = 0;
}
// Fill the lists
for (i = 0 ; i < N ; i++) {
int listNo;
listNo = (H - h[i])/U;
//if (lists[listNo] -> noOfElements < (listNo + 1)) {
listInsertDesc(lists[listNo],N,newNode(h[i],w[i],NULL));
// lists[listNo] -> noOfElements++;
//}
}
/*
// print lists
for (i = 0 ; i < noOfLists ; i++) {
printf("lista %d:\n",i);
printList(lists[i]);
}
*/
//linkedList selected = (linkedList) malloc (sizeof(node));
free(h);
free(w);
BTree * aBTree = (BTree*) malloc(sizeof(BTree));
aBTree -> nodes = NULL;
int listCount = 0;
for (i = 0 ; i < noOfLists ; i++) {
while (isEmpty(lists[i]) == false) {
//listInsertAsc(selected,i + 1,getNextNode(lists[i]));
node *tempNode = getNextNode(lists[i]);
add(aBTree,newBNode(tempNode -> h,tempNode -> w));
listCount ++;
//printf("Lista dupa inserare: \n");
//printList(selected);
if (listCount > i + 1) {
delMin(aBTree);
// printf("pas = %d, dim lista = %d, Lista dupa stergere: \n",i + 1,listCount);
// printList(selected);
listCount --;
}
}
}
/*add(aBTree,newBNode(100,10));
add(aBTree,newBNode(200,20));
add(aBTree,newBNode(10,15));
add(aBTree,newBNode(250,25));
add(aBTree,newBNode(10,30));
add(aBTree,newBNode(250,24));
printBTree(aBTree -> nodes);
delMin(aBTree);
printf("\n");
printBTree(aBTree -> nodes);*/
// printBTree(aBTree -> nodes);
//printf("lista finala:\n");
//printList(selected);
unsigned long long suma = 0;
//while (isEmpty(selected) == false) {
//node *tempNode = getNextNode(selected);
countValues(aBTree -> nodes, &suma);
//suma += tempNode -> w;
// printf("%d %d\n",tempNode -> h,tempNode -> w);
//}
//printBTree(aBTree->nodes);
fprintf(fout,"%lld\n",suma);
//printf("%lld\n",suma);
fclose(fin);
fclose(fout);
return 0;
}