#include <stdio.h>
#include <algorithm>
#include <vector>
using namespace std;
struct fructa
{
long h, g, n;
// h = inaltimea la care se afla gutuia
// g = greutatea gutuii
// n = numarul maxim de gutui care pot fi culese inainte ce aceasta
// sa poata fi culease
// n = [ (H - h) / U ] ( [ ] = parte intreaga)
};
fructa f[100000];
int cmpN(const void * p, const void * q)
// functia cmpN ("compara-n") va fi apelata cu parametrii de tip fructa
// este corespunzatoare relatiei de ordine dupa care se sorteaza vectorul f[]
// fructaA "<=" fructaB daca fructaA.n <= fructaB.n (detalii despre motivele acestei alegeri in explicatia algoritmului)
{
fructa x = *(fructa*)p;
fructa y = *(fructa*)q;
return (x.n - y.n);
}
int cmpG(long p, long q)
// functia cmpG ("compara-g") va fi apelata cu parametrii de tip long
// compara fructele ce au drept indici parametrii dati, dupa greutate
// sta la baza realizarii structurii de heap in vectorul sol
// cmpG(p, q) intoarce "1" daca f[p] este mai greu decat f[q], si "0" in caz contrar
// prin urmare, vectorul sol va fi un min-heap raportat la greutatea fructelor
{
fructa x = f[p];
fructa y = f[q];
if (x.g > y.g )
{
return 1;
}
else
{
return 0;
}
}
int main()
{
long nSol=0, H, N, U;
// nSol = numarul de elemente din solutia curenta
// H, N, U sunt conform enuntului
long gSol=0, i, k;
// gSol = greutatea solutiei curente
// altfel spus, suma greutatilor gutuilor din solutia curenta
vector<long> sol;
vector<long>::iterator it;
// sol = solutia curenta; in sol se retin indicii (din f[]) ai fructelor
FILE *fin, *fout;
fin = fopen("gutui.in", "r");
fout = fopen("gutui.out", "w");
fscanf(fin, "%li%li%li", &N, &H, &U);
// scanf("%li%li%li", &N, &H, &U);
for(i=0;i<N;i++)
{
fscanf(fin, "%li%li", &f[i].h, &f[i].g);
// scanf("%li%li", &f[i].h, &f[i].g);
f[i].n = (H-f[i].h) / U;
}
qsort(f, N, sizeof(fructa), cmpN);
// se sorteaza vectorul de fructe dupa n (definit in structura fructa)
// se parcurce vectorul de fructe incepand de la 0
for(k=0;k<N;k++)
{
// se compara n-ul fructei f[k] cu numarul de elemente din solutia curenta
// nSol = numarul de elemente din sol (solutia curenta)
if(f[k].n >= nSol) // daca f[k].n >= nSol , inseamna ca putem adauga fructa f[k] la solutia curenta
{
sol.push_back(k); // adaugam indicele k in vectorul sol
push_heap( sol.begin(), sol.end(), cmpG ); // refacem structura de heap a vectorului sol
nSol++; // incrementam nSol (deoarece am adaugat un element in solutie)
gSol += f[k].g; // actualizam greutatea solutiei (adaugand greutatea fructei f[k])
}
else // daca f[k].n < nSol , atunci conform explicatiilor algoritmului, f[k].n = nSol - 1
// in acest caz, cautam elementul cu greutatea minima din solutie si vedem daca trebuie sa il
// inlocuim cu f[k] sau nu (in functie de care are greutatea mai mare)
if (f[sol.front()].g < f[k].g)
// daca greutatea lui f[k] este mai mare decat greutatea "minimului" din solutie, atunci
// il vom elimina pe acest minim din solutie si il vom adauga pe f[k]
{
// datorita structurii de heap a lui sol, f[sol.front()] este elementul cu greutatea minima din solutie
gSol = gSol + f[k].g - f[sol.front()].g; // actualizam greutatea solutiei
pop_heap( sol.begin(), sol.end(), cmpG );
// pregatim eliminarea "minimului" punand indicele acestuia la coada lui sol
sol.pop_back();
// eliminam din sol indicele elementului minim
sol.push_back(k);
// adaugam incidele k in vectorul sol
push_heap( sol.begin(), sol.end(), cmpG );
// refacem structura de heap a vectorului sol
}
}
fprintf(fout, "%li", gSol);
// printf("%li", gSol); // afisarea solutiei
fclose(fin);
fclose(fout);
return 0;
}