pitici3

Pitici3

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

$N$ pitici (numerotaţi de la $1$ la $N$) au căzut într-o groapă adâncă de $D$ cm. Fiecare pitic îşi cunoaşte înălţimea umerilor (adică distanţa de la pământ la umerii săi), precum şi lungimea braţelor. Prin urmare, dacă piticul $i$ ( $1 ≤ i ≤ N$ ) are înălţimea umerilor $H{~i~}$ cm şi lungimea braţelor $L{~i~}$ cm, atunci când el va sta în picioare cu braţele în sus va atinge înălţimea $H{~i~}+L{~i~}$ cm.

$N$ pitici (numerotaţi de la $1$ la $N$) au căzut într-o groapă adâncă de $D$ cm. Fiecare pitic îşi cunoaşte înălţimea umerilor (adică distanţa de la pământ la umerii săi), precum şi lungimea braţelor. Prin urmare, dacă piticul $i$ ( $1 ≤ i ≤ N$ ) are înălţimea umerilor $H{~i~}$ cm şi lungimea braţelor $L{~i~}$ cm, atunci când el va sta în picioare cu braţele în sus va atinge înălţimea $H{~i~} + L{~i~}$ cm.

Piticii se pot urca unii pe umerii celorlalţi formând astfel un singur turn. Dacă piticul $i$ stă cu mânile întinse şi este urcat pe umerii piticului $j{~k~}$, care stă pe umerii lui $j{~k-1~}$, ... care stă pe umerii lui $j{~1~}$ atunci el va atinge înălţimea $H{~j1~}$ + $H{~j2~}$ + … + $H{~jk~}$ + $H{~i~}$ + $L{~i~}$.

h2. Date de intrare

Fişierul de intrare $pitici3.in$ conţine pe prima linie numărul natural $N$ reprezentând numărul de pitici. Pe următoarele $N$ linii sunt descrişi piticii. Mai exact, pe linia $i+1$ se află două numere naturale separate prin spaţiu $H{~i~}$ şi $L{~i~}$ reprezentând înălţimea umerilor şi respectiv lungimea braţelor piticului $i$ ( $1 ≤ i ≤ N$). Pe ultima linie este scris un număr natural $D$ reprezentând adâncimea gropii.

Fişierul de intrare $pitici3.in$ conţine pe prima linie numărul natural $N$ reprezentând numărul de pitici. Pe următoarele $N$ linii sunt descrişi piticii. Mai exact, pe linia $i+1$ se află două numere naturale separate prin spaţiu $H{~i~}$ şi $L{~i~}$ reprezentând înălţimea umerilor şi respectiv lungimea braţelor piticului $i$ ( $1 ≤ i ≤ N$ ). Pe ultima linie este scris un număr natural $D$ reprezentând adâncimea gropii.

h2. Date de ieşire

h2. Restricţii
* $1 ≤ N ≤ 2000$

* $1 ≤ H{~i~} ≤ 105 (1 ≤ i ≤ N)$
* $1 ≤ L{~i~} ≤ 105 (1 ≤ i ≤ N)$
* $1 ≤ D ≤ 105$

* $1 ≤ H{~i~} ≤ 10^5^ (1 ≤ i ≤ N)$
* $1 ≤ L{~i~} ≤ 10^5^ (1 ≤ i ≤ N)$
* $1 ≤ D ≤ 10^5^$

* Piticii care ies nu mai intră înapoi.
* Pentru $70%$ din teste $N ≤ 100$ ; $D, H{~i~}, L{~i~} ≤ 1000$.

h3. Explicaţie

De exemplu, pot ieşi piticii $1$ $5$ si $6$.

De exemplu, pot ieşi piticii $1$, $5$ si $6$.

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

3792