Fişierul intrare/ieşire:	pitici3.in, pitici3.out	Sursă	Lot Iasi 2008, Baraj 5
Autor	Emanuela Cerchez	Adăugată de	Pripoae Teodor Anton •toni2007
Timp execuţie pe test	0.05 sec	Limită de memorie	20480 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

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.

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₁ 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ă.

Cerinţă

Să se determine numărul maxim de pitici care pot ieşi din groapă.

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.

Date de ieşire

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

Restricţii

• 1 ≤ N ≤ 2000
• 1 ≤ H_i ≤ 10⁵ (1 ≤ i ≤ N)
• 1 ≤ L_i ≤ 10⁵ (1 ≤ i ≤ N)
• 1 ≤ D ≤ 10⁵
• Piticii care ies nu mai intră înapoi.
• Pentru 70% din teste N ≤ 100 ; D, H_i, L_i ≤ 1000.

Exemplu

Explicaţie

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

Cum se trimit solutii?