== 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~}$.
Dacă un pitic atinge marginea gropii (adică $H{~j1~}$ + $H{~j2~}$ + … + $H{~jk~}$ + $H{~i~}$ + $L{~i~}$ ≥ D), el poate ieşi din groapă.
h2. Cerinţă
Să se determine numărul maxim de pitici care pot ieşi din groapă.
h2. Date de intrare
Fişierul de intrare $pitici3.in$ ...
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
În fişierul de ieşire $pitici3.out$ ...
Fişierul de ieşire $pitici3.out$ va conţine o singură linie pe care va fi scris numărul natural $X$ reprezentând numărul maxim de pitici care pot ieşi din groapă.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $1 ≤ N ≤ 2000$
* $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$.
h2. Exemplu
table(example). |_. pitici3.in |_. pitici3.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 7
2 4
3 2
4 1
7 5
2 1
6 4
6 1
30
| 3
|
h3. Explicaţie
...
De exemplu, pot ieşi piticii $1$, $5$ si $6$.
== include(page="template/taskfooter" task_id="pitici3") ==
