Lupul Urias si Rau

lupu

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

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

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

Poveste ...

h2. Cerinta

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

...

h2. Date de Intrare

h2. Restrictii

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 Iesire

h2. Date de intrare

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. Restrictii si precizari

h2. Date de iesire

* $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

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")==
 

| lupu.in | lupu.out |
| linia1
linia2
linia3
| linia1
linia2
|
== include(page="template/taskfooter" task_id="lupu") ==

927