#include<stdio.h>
#include<malloc.h>
int *c,*d;
typedef struct {
int inaltime;
int greutate;
} gutuie;
//interschimba 2 elemente din vectorul de gutui
void swap(gutuie *a, gutuie *b) {
gutuie aux;
aux=*a;
*a=*b;
*b=aux;
}
void swap2(int *a, int *b) {
int temp;
temp=*a;
*a=*b;
*b=temp;
}
//auxiliar pentru functia de sortare quicksort
int choose_pivot(int i, int j) {
return ((i+j)/2);
}
//sorteaza descrescator in functie de greutate in vectorul de gutui
void qsort(gutuie *g, int m, int n) {
int key,i,j,k;
if (m<n)
{
k=choose_pivot(m,n);
swap(&g[m],&g[k]);
key=g[m].greutate;
i=m+1;
j=n;
while (i<=j)
{
while ((i<=n)&&(g[i].greutate>=key))
i++;
while ((j>=m) &&(g[j].greutate<key))
j--;
if (i<j)
swap(&g[i],&g[j]);
}
swap(&g[m],&g[j]);
qsort(g,m,j-1);
qsort(g,j+1,n);
}
}
void merge (int *ind, int *ord, int *c, int *d, int low, int high, int mid);
void mergesort(int *ind, int * ord, int *c, int *d, int low, int high) {
int mid;
if (low<high)
{
mid=(low+high)/2;
mergesort(ind, ord, c,d,low, mid);
mergesort(ind, ord, c,d,mid+1, high);
merge(ind, ord, c,d,low, high, mid);
}
return;
}
void merge(int *ind, int *ord, int *c, int *d, int low, int high, int mid) {
int i,j,k;
i=low;
j=mid+1;
k=low;
while((i<=mid)&&(j<=high))
{
if (ord[i]<=ord[j])
{
c[k]=ord[i];
d[k]=ind[i];
k++;
i++;
}
else
{
c[k]=ord[j];
d[k]=ind[j];
k++;
j++;
}
}
while (i<=mid)
{
c[k]=ord[i];
d[k]=ind[i];
k++;
i++;
}
while (j<=high)
{
c[k]=ord[j];
d[k]=ind[j];
k++;
j++;
}
for (i=low;i<k;i++) {
ord[i]=c[i];
ind[i]=d[i];
}
}
void qsort2(int *ind, int *ord,int m, int n) {
int key,i,j,k;
if (m<n)
{
k=choose_pivot(m,n);
swap2(&ind[m],&ind[k]);
swap2(&ord[m],&ord[k]);
key=ord[m];
i=m+1;
j=n;
while (i<=j)
{
while ((i<=n)&&(ord[i]<=key))
i++;
while ((j>=m) &&(ord[j]>key))
j--;
if (i<j) {
swap2(&ind[i],&ind[j]);
swap2(&ord[i],&ord[j]);
}
}
swap2(&ind[m],&ind[j]);
swap2(&ord[m],&ord[j]);
qsort2(ind,ord,m,j-1);
qsort2(ind,ord,j+1,n);
}
}
int main() {
//DECLARARI VARIABILE
int n,h,u,i,j,gt=0;
FILE *in=fopen("gutui.in","r");
FILE *out=fopen("gutui.out","w");
fscanf(in,"%d",&n);
//ALOCARI DE MEMORIE
gutuie *g=(gutuie*)malloc(n*sizeof(gutuie));
int *ord=(int*)malloc(n*sizeof(int));
int *ind=(int*)malloc(n*sizeof(int));
int *c=(int*)malloc(n*sizeof(int));
int *d=(int*)malloc(n*sizeof(int));
//CITIRE DIN FISIER SI COMPLETARE CAMPURI GUTUI
fscanf(in,"%d%d",&h,&u);
for (i=0;i<n;i++)
fscanf(in,"%d%d",&g[i].inaltime,&g[i].greutate);
/*
for (i=0;i<n;i++)
printf("%d %d\n",g[i].inaltime,g[i].greutate);
printf("\n");
*/
qsort(g,0,n-1);
/*
for (i=0;i<n;i++)
printf("%d %d\n",g[i].inaltime,g[i].greutate);
printf("\n");
*/
int m=-1,hmax=0,hmin=g[0].inaltime,aux,p;
for (i=0;i<n;i++) {
if (g[i].inaltime>hmax) hmax=g[i].inaltime;
if (g[i].inaltime<hmin) hmin=g[i].inaltime;
}
//printf("max=%d\nmin=%d\n",max,min);
//max=(h-max)/u;
//for (i=0;i<n;i++) ordine_cules[i]=0;
int acc,inplus;
acc=(h-hmin)/u+1;
inplus=(h-hmax)/u;
for (i=0;i<n;i++) {
ind[i]=i;
ord[i]=(h-g[i].inaltime)/u;
}
/*
for (i=0;i<n;i++)
printf("%d ",ind[i]);
printf("\n");
for (i=0;i<n;i++)
printf("%d ",ord[i]);
printf("\n");
*/
//qsort2(ind,ord,0,n-1);
mergesort(ind,ord,c,d,0,n-1);
/*
for (i=0;i<n;i++)
printf("%d ",ind[i]);
printf("\n");
for (i=0;i<n;i++)
printf("%d ",ord[i]);
printf("\n");
*/
printf("acc=%d\n",acc);
for (i=0;i<n;i++) {
if (i==0 && acc>0) {
gt+=g[ind[i]].greutate;
acc--;
}
else
if (ord[i]==ord[i-1]) {
if (inplus>0 && acc>0)
{
gt+=g[ind[i]].greutate;
inplus--;
acc--;
}
}
else
{
gt+=g[ind[i]].greutate;
acc--;
}
}
/*
for (i=0;i<n;i++) {
p=(h-g[i].inaltime)/u-max;
if (ordine_cules[p]==0) ordine_cules[p]=i+1;
else
{
aux=p+1;
while (ordine_cules[aux]!=0) aux++;
ordine_cules[aux]=i+1;
if (m<aux) m=aux;
}
}
printf("nr.el=%d\n",aux+1);
for (i=0;i<n;i++)
printf("%d ",ordine_cules[i]);
printf("\n");
for (i=0;i<(h-min)/u+1;i++)
gt+=g[ordine_cules[i]-1].greutate;
*/
/*
while (ordine_cules[(h-g[i].inaltime)/u][c]!=0) c++;
ordine_cules[(h-g[i].inaltime)/u][c]=i+1;
}
/*
for (i=0;i<n;i++) {
for (j=0;j<n;j++)
printf("%d ",ordine_cules[i][j]);
printf("\n");
}
for (i=0;i<n;i++)
for (j=0;j<=i;j++)
if (ordine_cules[i][j]!=0)
gt+=g[ordine_cules[i][j]-1].greutate;
*/
fprintf(out,"%d\n",gt);
return 0;
}