#include <stdio.h>
#include <string.h>
void swap (long a, long b)
{
long aux;
aux=a;
a=b;
b=aux;
}
// nr gutui, inaltimea maxima, inaltarea, rezultatul final
long n, hi, u, smax=0;
// inantimea fiecarei gutui si greutatea
long h[100001], w[100001], i, j, aux, max, im;
long hmin, nrs, k, s[100001], contor, x, y;
//imparte fructele in sectoare
void sectoare()
{
for(k=1; k<=nrs; k++)
for(i=0; i<n; i++)
if(h[i]+k*u>hi && h[i]+(k-1)*u<=hi)
{
s[i]=k;
}
}
//indicele fructului cu greutate maxima de pe sectorul k
long imax (long k)
{
im=-100;
max=-300;
for(i=0; i<n; i++)
if(w[i]>max && s[i]==k)
{
im=i;
max=w[i];
}
return im;
}
//indicele fructului cu greutate maxima de pe sectoarele 1-k
long imax1 (long k)
{
im=-100;
max=-300;
for(i=0; i<n; i++)
if(w[i]>max && 1<=s[i] && s[i]<=k)
{
im=i;
max=w[i];
}
return im;
}
// verifica daca pe sectorul k sunt cel putin k elemente mai grele decat elementul x
int verifica(long x, long k)
{
contor=0;
for(i=0; i<n; i++)
if(w[i]>w[x] && s[i]==k)
contor++;
if(contor>=k)
return 1;
else
return 0;
}
//culege fructul cu indicele y, cu toate urmarile
void culege(long y)
{
if(y>=0 && w[y]>=0)
{
smax+=w[y];
w[y]=-500;
for(i=0; i<n; i++)
{
h[i]+=u;
if(h[i]>hi)
w[i]=-500;
}
}
}
int main()
{
int done, flag;
FILE *f=fopen("gutui.in", "r");
FILE *g=fopen("gutui.out", "w");
fscanf(f, "%ld %ld %ld", &n, &hi, &u);
for(i=0; i<n; i++)
fscanf(f, "%ld %ld", &h[i], &w[i]);
/* for(i=0; i<n; i++)
printf("fructul %ld are inaltimea %ld si greutatea %ld\n", i, h[i], w[i]);
*/
//sortam descrescator fructele, in functie de inaltime
//trebuie inlocuit cu quicksort, de exemplu
for(i=0; i<n-1; i++)
for(j=i+1; j<n; j++)
if(h[i]<h[j])
{
//swap(h[i], h[j]);
//swap(w[i], w[j]);
aux=h[i];
h[i]=h[j];
h[j]=aux;
aux=w[i];
w[i]=w[j];
w[j]=aux;
}
printf("Dupa quicksort: \n");
for(i=0; i<n; i++)
printf("fructul %ld are inaltimea %ld si greutatea %ld\n", i, h[i], w[i]);
hmin=h[n-1];
printf("hmin este: %ld\n", hmin);
//pana aici sigur e bine
nrs=(hi-hmin)/u+1;
printf("numarul de sectoare este: %ld\n", nrs);
//the core shit
done=0;
//cat timp n-am terminat
while(done==0)
{
flag=0;
//(re)impartim fructele in sectoare, in functie de inaltimile curente
sectoare();
k=nrs;
//daca pe sectorul k sunt k elemente mai grele decat elementul x
while(k>1)
{
// indicele elementului maxim de pe sectoarele 1-(k-1)
x=imax1(k-1);
//daca are valoarea -100 inseamna ca nu exista niciun element pe sectorul 1-(k-1)
// in acest caz se culege maximul din intreaga multime ( sau poate ar trebui 1-k?)
if(x<0)
{
max=-200;
im=-100;
for(i=0; i<n; i++)
if(w[i]>max && 1<=s[i]<=k)
{
im=i;
max=w[i];
}
culege(im);
flag=1;
break;
}
else
{
//daca pe sectorul k sunt k elemente mai grele decat elementul x
if(verifica(x, k)==1)
break;
k--;
}
}
//daca n-am gasit o astfel de situatie, culegem greutatea maxima de pe sectorul 1
if(flag==0)
{
if(k==1)
{
culege(x);
}
//daca am gasit o astfel de situatie, culegem greutatea maxima de pe sectorul k
else
{
y=imax(k);
culege(y);
}
}
done=1;
for(i=0; i<n; i++)
if(h[i]<=hi)
done=0;
}
fprintf(g, "%ld", smax);
fclose(f);
fclose(g);
return 0;
}