lupu

Lupul Urias si Rau

== include(page="template/taskheader" task_id="lupu") ==

==Include(page="template/taskheader" task_id="lupu")==

Poveste ...

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).

h2. Cerinta

...

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

h2. Restrictii

h2. 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.

h2. Date de intrare

h2. 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.

h2. Date de iesire

h2. 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^31^-1$}]

h2. Exemplu

| lupu.in | lupu.out |
| linia1
linia2
linia3
| linia1
linia2
|

table(example). |_. lupu.in |_. lupu.out |
| 10 6 2
1 13
4 14
4 3
6 7
0 7
5 16
3 16
4 10
4 18
3 16
| 54 |
 
 
==Include(page="template/taskfooter" task_id="lupu")==
 

== include(page="template/taskfooter" task_id="lupu") ==

927