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 daparteaza 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

o 1 <= N <= 100.000
o Pentru 40% din teste N <= 1000
o Toate numerele din fisierul de intrare sunt intregi din intervalul [0, 2^31-1]

...

h2. Exemplu

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

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

 
 
References
 
Visible links
1. file:///home/eval/eval/www/infoarena/docs/arhiva/lupu/enunt.files/filelist.xml
==Include(page="template/taskfooter" task_id="lupu")==

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