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 Hi cm şi lungimea braţelor Li cm, atunci când el va sta în picioare cu braţele în sus va atinge înălţimea Hi+Li 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 jk, care stă pe umerii lui jk-1, ... care stă pe umerii lui j1 atunci el va atinge înălţimea Hj1+Hj2 +…+Hjk+Hi+Li.
Dacă un pitic atinge marginea gropii (adică Hj1 + Hj2 +… + Hjk+Hi+Li ≥ 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 pitici.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 Hi şi Li 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 pitici.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 ≤ Hi ≤ 105 (1 ≤ i ≤ N)
1 ≤ Li ≤ 105 (1 ≤ i ≤ N)
1 ≤ D ≤ 105
Piticii care ies nu mai intră înapoi.
Pentru 70% din teste N ≤ 100; D, Hi, Li ≤ 1000.