Indiferent de codificarea datelor necesare pentru memorarea coordonatei, piese de domino de diferite înălţimi sunt aşezate în dreptul unor coordonate, marcate de-a lungul unei linii drepte trasată pe o suprafaţă plană. Acţionând asupra unei piese, aceasta poate antrena în cădere la stânga sau la dreapta, un şir de alte piese, piese ce vor cădea unele peste altele. O piesă este doborâtă de o altă piesă dacă este atinsă în cădere de aceasta, chiar şi numai la baza ei, fiind astfel posibil ca şi o piesă mai mică să doboare o alta mai mare, dacă este atinsă de aceasta în cădere.
Cerinţă:
Determinaţi lungimea maximă a unui şir de piese căzute care se obţine prin acţionarea unei piese într-un anumit sens. Aceasta este cea mai mare lungime pe orizontală acoperită integral de piese căzute.
Date de intrare
Fişierul de intrare domino.in conţine pe prima linie , numărul de piese iar pe fiecare din următoarele linii, coordonata la care se află piesa şi înălţimea acesteia, despărţite printr-un spaţiu.
Date de ieșire
Fişierul de ieşire domino.out conţine pe prima linie un număr natural reprezentând lungimea maximă a şirului de piese căzute.
Restricții și precizări
- Suprafaţa este suficient de mare pentru ca piesele să nu cadă în afara ei.
- Numărul de piese , este un număr natural din intervalul []
- Înălţimea unei piese este un număr natural din intervalul []
Exemplul 1
domino.in
5
40 1
8 2
30 4
1 6
4 11
domino.out
14
Explicație
Lungimea celui mai lung şir de piese căzute este egală cu şi se obţine prin acţionarea spre dreapta a piesei aşezate la coordonata , care va antrena în cădere piesa de la coordonata iar aceasta la rândul ei pe cea de la coordonata .
Exemplul 2
domino.in
6
53 3
62 4
15 5
20 6
60 8
75 9
domino.out
12
Explicație
Lungimea celui mai lung şir de piese căzute este egală cu şi se obţine prin acţionarea spre stânga a piesei aşezate la coordonata , care va antrena în cădere piesa de la coordonata iar aceasta la rândul ei pe cea de la coordonata .