#include <fstream>
#include <stdlib.h>
using namespace std;
struct gutuie {
int g; // greutatea
int n; // nr max de gutui culese anterior pt care gutuia ramane accesibila, numit "nivel"
int idx; // indexul
};
#define S (sizeof(gutuie))
ifstream in ("gutui.in");
ofstream out("gutui.out");
int n, h, u, r = 0, nr = 0, *del;
gutuie *gutui, *gutui2;
// comparara dupa nivel
int cmp_n(const void* fp1, const void* fp2) {
gutuie* f1 = (gutuie*)fp1;
gutuie* f2 = (gutuie*)fp2;
int r = f1->n - f2->n;
return (r == 0 ? f2->g - f1->g : r);
}
// comparara dupa greutate
int cmp_g(const void* fp1, const void* fp2) {
gutuie* f1 = (gutuie*)fp1;
gutuie* f2 = (gutuie*)fp2;
int r = f1->g - f2->g;
return (r == 0 ? f1->n - f2->n : r);
}
void print() {
for (int i = 0; i < n; i++) {
printf("%9d %d %d %9d %d %d\n", gutui[i].g, gutui[i].n, gutui[i].idx, gutui2[i].g, gutui2[i].n, gutui2[i].idx);
}
printf("\n");
}
int main() {
in >> n >> h >> u;
gutui = new gutuie[n];
int ch, cg, cn, cnr, i, j, k, rem;
/* - citire din fisier
* - o prima selectie - selectatrea cazurilor convenabile, adica
* eliminarea gutuilor la care nu se poate ajunge din prima , adica nivelul < 0 si
* a celor cu greutate nula (daca exista)
* - nr gutuilor ramase dupa aceasta prima selectie fiind nr <= n
*/
for (i = 0; i < n; i++) {
in >> ch >> cg; // citire inaltime si greutate
cn = (h - ch) / u; // calcul nivel
if (cn >= 0 && cg > 0) { // se adauga numai cazurile convenabile
r += cg;
gutui[nr].g = cg;
gutui[nr].n = cn;
nr++;
}
}
n = nr;
if (n == 0) {
out << r;
return 0;
}
// sortare dupa nivel; pt acelasi nivel, se vor sorta in ordine descrescatoare a greutatii
qsort(gutui, n, S, cmp_n);
/* o noua selectie, considerand ca
* se pot face maxim k + 1 culegeri de gutui aflate la nivelul k
* daca exista mai mult de k + 1 gutui aflate la nivelul k, se pastreaza cele mai grele k + 1
*/
i = 0, cn = 0, cnr = 0;
rem = 0; // nr de gutui eliminate
while (i < n) {
if (gutui[i].n == cn) {
cnr++;
if (cnr > cn + 1) { // incepand cu cn + 2, se vor elimina toate gutuile cu nivelul curent
while (gutui[i].n == cn && i < n) {
r -=gutui[i].g;
gutui[i].g = 0;
i++;
rem++;
}
}
else {
i++;
}
}
else {
cn = gutui[i].n;
cnr = 1;
i++;
}
}
// sortare dupa greutate
qsort(gutui, n, S, cmp_g);
// eliminarea celor a caror greutate a fost setata pe 0, dupa selectia a 2 a
gutui += rem;
n -= rem;
if (n == 0) {
out << r;
return 0;
}
qsort(gutui, n, S, cmp_n);
for (i = 0; i < n; i++)
gutui[i].idx = i;
qsort(gutui, n, S, cmp_g);
gutui2 = new gutuie[n];
for (i = 0; i < n; i++) {
gutui2[i] = gutui[i];
gutui2[i].idx = i;
}
qsort(gutui2, n, S, cmp_n);
del = new int[gutui2[n - 1].n];
for (i = 0; i < gutui2[n - 1].n; i++)
del[i] = 0;
/* gutui - sortat dupa greutate
* gutui2 - sortat dupa nivel
* gutui[i] .idx = indexul elementului gutui [i] in vectorul gutui2
* gutui2[i].idx = indexul elementului gutui2[i] in vectorul gutui
*/
// print();
i = 0, // indicele elementului curent cu greutate minima din gutui
j = n-1; // indicele elementului curent cu nivel maxim din gutui2
if (j == 0) {
out << r;
return 0;
}
while (1) {
again:
if (j <= 1) {
out << r;
return 0;
}
cn = gutui2[j].n; // nivelul curent
cnr = 0; // nr de gutui de pe nivelul curent
nr = 0;
rem = j - cn; // nr de gutui care trebuiesc eliminate dupa analiza nivelului curent
if (rem <= 0) {
while (gutui2[j - nr].n == cn) {
gutui[gutui2[j - nr].idx].g = 0;
nr++;
}
j -= nr;
goto again;
}
while (gutui2[j - nr].n == cn) {
if (gutui2[j - nr].g != 0) { // daca nu a fost deja verificata
if (cn >= j - nr - del[cn]) { // daca se poate culege,
gutui2[j - nr].g = 0; // se va seta ca si verificata, adica oricum se va culege
gutui[gutui2[j - nr].idx].g = 0;
rem--;
}
}
else
rem--;
nr++;
}
j -= nr;
// trebuiesc eliminate "rem" gutui, eliminarea facandu-se in ordinea crescatoare a greutatii
while (rem) {
if (gutui[i].g) {
r -= gutui[i].g;
gutui[i].g = 0;
gutui2[gutui[i].idx].g = 0;
for (k = gutui[i].n; k <= cn; k++)
del[k]++;
rem--;
}
i++;
}
}
out << r;
return 0;
}