#include <stdio.h>
#include <stdlib.h>
#define N_MAX 100000
void Afis(int gutui[2][N_MAX],int n)
{
int i=0;
for (;i<n;i++)
printf("%i:%i\n",gutui[0][i],gutui[1][i]);
}
void swap(int *x,int *y,int *z,int *q)
{
int temp;
temp = *x;
*x = *y;
*y = temp;
temp = *z;
*z = *q;
*q = temp;
}
int choose_pivot(int i,int j )
{
return((i+j) /2);
}
void quicksort(int list[2][N_MAX],int m,int n,int crit)
{
int key,i,j,k;
if( m < n)
{
k = choose_pivot(m,n);
swap(&list[1][m],&list[1][k],&list[0][m],&list[0][k]);
key = list[crit][m];
i = m+1;
j = n;
while(i <= j)
{
while((i <= n) && (list[crit][i] <= key))
i++;
while((j >= m) && (list[crit][j] > key))
j--;
if( i < j)
swap(&list[0][i],&list[0][j],&list[1][i],&list[1][j]);
}
// swap two elements
swap(&list[0][m],&list[0][j],&list[1][m],&list[1][j]);
// recursively sort the lesser list
quicksort(list,m,j-1,crit);
quicksort(list,j+1,n,crit);
}
}
void printlist(int list[2][N_MAX],int n)
{
int i;
for(i=0;i<n;i++)
printf("%d:%d\n",list[0][i],list[1][i]);
printf("\n");
}
void FindMax(int list[2][N_MAX],int n,int b,int *x)
{
int max=list[1][n-1];
int i;
*x=n-1;
*(x+1)=list[0][n-1];
for(i=n-2;i>=b;i--)
if(max<=list[1][i])
{
max=list[1][i];
*x=i;
*(x+1)=list[0][i];
}
}
void FindHMax(int list[2][N_MAX],int n,int b,int *x)
{
*x=n-1;
int i;
for(i=n-2;i>=b;i--)
if(list[0][*x]<=list[0][i])
*x=i;
}
int Accesibile(int pozMax,int hMax,int u)
{
return hMax/u-pozMax/u;
}
void Inc(int list[2][N_MAX],int n,int u)
{
int i=0;
for (;i<n;i++)
list[0][i]+=u;
}
void Remove(int list[2][N_MAX],int n,int poz)
{
int i;
for(i=poz;i<n-1;i++)
{
list[0][i]=list[0][i+1];
list[1][i]=list[1][i+1];
}
}
int Suma(int list[2][N_MAX],int n,int h,int u)
{
int pozMax[2];
int s=0;
FindMax(list,n,0,pozMax);
//printf("%i?|?%i\n",pozMax[0],pozMax[1]);
int acces=Accesibile(pozMax[1],h,u);
//printf("ACCESIBILE: %i\n",acces);
int i=0;
if (pozMax[0]!=n-1)
{
quicksort(list,pozMax[0],n-1,1);
//printlist(list,n);
//printf("urmeaza WHILE\n");
while(i<acces)
{
//printlist(list,n);
s=s+list[1][n-1-i];
i++;
}
n=n-acces;
for(i=0;i<acces;i++)
Inc(list,n,u);
int j;
for(j=0;j<n;j++)
if(list[0][j]>h)
{
//printf("**a scos %i||%i **\n\n",list[0][j],list[1][j]);
Remove(list,n,j);
j--;
n-=1;
}
//printlist(list,n);
}
else
{
s=list[1][pozMax[0]];
Inc(list,n,u);
int j;
for(j=0;j<n;j++)
if(list[0][j]>h)
{
//printf("**a scos %i||%i **\n\n",list[0][j],list[1][j]);
Remove(list,n,j);
j--;
n-=1;
}
}
//printf("$$SUMA CURENTA %i $$\n\n",s);
if(n>0)
return s+Suma(list,n,h,u);
return s;
}
int main()
{
FILE *f;
int n,h,u,i,x,y;
f=fopen("gutui.in","r");
fscanf(f,"%i %i %i",&n,&h,&u);
//printf("%i %i %i\n",n,h,u);
int gutui[2][N_MAX];
for(i=0;i<n;i++)
{
fscanf(f,"%i %i",&x,&y);
gutui[0][i]=x;
gutui[1][i]=y;
}
close(f);
//Afis(gutui,n);
//printf("\n");
quicksort(gutui,0,n-1,0);
//printlist(gutui,n);
//printf("\n");
//int pozMax[2];
//printf("\n");
//printf("\n");
x=Suma(gutui,n,h,u);
FILE *g;
g=open("fis.out","w");
fprintf(g,"suma: %i",x);
close(g);
return 0;
}