Lupul Urias si Rau

Lupul Urias si Rau

Lupul urias si rau isi doreste sa se poata juca cu prietenele sale oitele mici si pufoase. In calea fericirii sale sta insa ciobanasul Eduard care decide sa nu-l lase pe lup sa se joace cu toate oile sale, il lasa sa aleaga doar cateva. Lupul se afla intr-un punct fix pe pajiste, iar oile stau la diferite distante fata de el. Alegerea oilor se face in mai multe etape. Lupul urias si rau alege o oaie aflata la o distanta de maxim X si in acel moment toate celelalte oi se vor indeparta (la cerintele ciobanasului Eduard) cu distanta L fata de lup. Pentru fiecare oaie se cunoaste cantitatea de lana pe care o are, iar lupul isi doreste ca suma cantitatilor de lana pentru oile alese sa fie cat mai mare (ca sa fie cat mai pufoase).

Cerinta

Ajutati-l pe lupul urias si rau sa aleaga oile astfel incat sa aiba cat mai multa lana.

Date de Intrare

Prima linie a fisierului de intrare lupu.in contine trei numere intregi N , X si L reprezentand numarul de oi, distanta maxima de la care lupul poate alege oi si distanta cu care se departeaza oile de lup dupa fiecare alegere. Pe urmatoarele N linii se afla cate doua numere intregi D si A reprezentand distanta initiala si cantitatea de lana a fiecarei oi.

Date de Iesire

In fisierul lupu.out veti afisa un singur numar intreg S, reprezentand cantitatea maxima de lana pe care o poate aduna lupul de la oile alese.

Restrictii si precizari

• 
  1 ≤ N ≤ 100.000
  
• 
  Pentru 40% din teste N ≤ 1000
  
• 
  Toate numerele din fisierul de intrare sunt intregi din intervalul [0, 2³¹-1]
  

Exemplu

lupu.in
10 6 2 1 13 4 14 4 3 6 7 0 7 5 16 3 16 4 10 4 18 3 16

lupu.out va contine 54