#include<stdio.h>
#include<stdlib.h>
#include<iostream>
typedef struct lol{
unsigned long greutate;
unsigned long inaltime;
}lol;
lol *v;
unsigned nr_gutui,inalt_max,pas_inalt;
int key(int inaltime){
float x=inaltime;
return ((int)(x/pas_inalt)==x/pas_inalt)?((int)x/pas_inalt-1):(int)x/pas_inalt;
}
void citire(){
FILE *f=fopen("gutui.in","r");
fscanf(f,"%u %u %u",&nr_gutui,&inalt_max,&pas_inalt);
inalt_max=key(inalt_max);
//printf("%d\n\n\n",inalt_max);
//printf("%d %d %d\n",nr_gutui,inalt_max,pas_inalt);
v=(lol*)malloc(sizeof(lol)*nr_gutui);
//system("pause");
for(unsigned i=0;i<nr_gutui;i++)
{
fscanf(f,"%lu %lu",&v[i].inaltime,&v[i].greutate);
v[i].inaltime=key(v[i].inaltime);
//printf("%d %d\n",v[i].inaltime,v[i].greutate);
if(v[i].inaltime>inalt_max)
{
i--;
nr_gutui--;
continue;
}
//a=v[key(x)];
//v[key(x)]=(lol*)realloc(v[key(x)]);
//printf("%d\n\n",key(x));
}
fclose(f);
}
void afis(){
for(int i=0;i<nr_gutui;i++)
{
printf("%d %d\n",v[i].greutate,v[i].inaltime);
}
system("pause");
}
int compare (const void * a, const void * b)
{
return -( (*(lol*)a).greutate - (*(lol*)b).greutate );
}
void sortare(){
qsort (v, nr_gutui, sizeof(lol), compare);
}
int rezolvare(){
int s=v[0].greutate,cate_mai_pot=inalt_max-v[0].inaltime,inalt_act=v[0].inaltime;
for(int i=1;i<nr_gutui;i++){
//printf("\n\n%d %d\n",cate_mai_pot,inalt_act);
if(cate_mai_pot==0)
{
if(inalt_act>v[i].inaltime)
{
//printf("%c %d %d",'a',i,inalt_act);
s+=v[i].greutate;
cate_mai_pot=inalt_act-v[i].inaltime;
inalt_act=v[i].inaltime;
}
}
else
if(cate_mai_pot>0)
if(v[i].inaltime>inalt_act)
{
//printf("%c %d %d",'b',i,inalt_act);
s+=v[i].greutate;
cate_mai_pot--;
inalt_act++;
}
else
{
//printf("%c %d %d",'c',i,inalt_act);
s+=v[i].greutate;
cate_mai_pot--;
inalt_act++;
}
}
return s;
}
int funct(char *v,unsigned i)
{
for(;i<=inalt_max;i++)
if(v[i]==0)
return 1;
return 0;
}
int rezolvare2(){
char *vec=(char*)calloc(inalt_max+1,1);
unsigned long s=v[0].greutate,j;
vec[v[0].inaltime]=1;
for(unsigned i=1;i<nr_gutui;i++)
//printf("\n\n%d %d\n",cate_mai_pot,inalt_act);
if(funct(vec,v[i].inaltime)==1){
j=v[i].inaltime;
while(vec[j]==1)
j++;
s+=v[i].greutate;
vec[j]=1;
}
return s;
}
int main(){
FILE *g=fopen("gutui.out","w");
citire();
//afis();
sortare();
unsigned long s=rezolvare2();
fprintf(g,"%lu",s);
//printf("\n");
//afis();
fclose(g);
return 0;
}