Nosaukums
Akrobāts (akrobats)
Laika limits
1.00s
Atmiņas limits
32.0 MB
Grūtība
36%

Definīcija

Gudrinieku ciema akrobāts ir sasniedzis jau cienījamu vecumu, bet vēl joprojām nodarbojas ar veiklības paraugdemonstrējumiem. Viņa kroņa izrāde ir nepārspējami ātra tikšana uz zemes no augstas ēkas, kura sastāv no daudziem nelieliem jumtiņiem.

Draugiem grupa šogad organizē sacensības par godu Printful. Neskaitot dažādus programmētāju paraugdemonstrējumus, Draugiem group ir izlēmuši uzaicināt veco akrobātu parādīt savu kroņa izrādi. Lai gan vecais akrobāts vēl ir enerģijas pilns, viņš ir sācis raizētis par savu ceļu labklājību. Tādēļ viņš ir devies pie tevis, lai risinātu sekojošu problēmu - kā ar maksimāli daudz lēcieniem tikt līdz zemes līmenim (X = 0) un, rezultātā, saudzēt savus ceļus.

Uzdevumā ir dots jumtiņu izvietojums kā savstarpēji nekrustojošies nogriežņi plaknē. Tie vienmēr būs horizontāli un tos raksturos 3 skaitļi - Y jeb augstums, X jeb sākuma punkts, L jeb nogriežņa garums. Nav garantēts, ka jumtiņi ir doti augošā secībā pēc Y. Ir zināms, ka akrobāts neveic horizontālus lēcienus, tātad, ja jumtiņa B daļa vai punkts nav zem jumtiņa A, akrobāts pārvietoties no A uz B nevar. Lekšana no jumtiņa notiek tikai pa vienu no tā galiem.

Palīdzi akrobātam noskaidrot lielāko lēcienu skaitu, kurus jāveic, lai nokļūtu lejā no ēkas.


Ievaddatu raksturojums

Ievaddatu pirmajā rindā ir doti divi sakaitļi - jumtiņu skaits 1 <= N <= 100 000 un jumtiņa kārtas skaitlis 0 <= M < N, no kura akrobāts sāks savu izrādi.

Katrā nākamajā no N rindām doti 3 skaitļi - 0 <= X <= 1000, 1 <= Y <= 1000, 0 <= L <= 1000 (X, Y - jumtiņa nogriežņa kreisās malas koordinātes, L - jumtiņa nogriežņa garums).


Izvaddatu raksturojums

Izvaddatu pirmajā rindā jāizvada lielākais lēcienu skaits, kurus veicot, akrobāts var nokļūt no sākuma jumtiņa līdz zemei.


Paraugdati

Stdin
10 9
2 1 10
1 3 2
6 5 5
3 6 2
3 7 2
3 8 2
7 7 2
7 9 2
2 9 4
5 11 2
Stdout
5

Uzdevums tiek aizsargāts ar autortiesībām un tā kopēšana vai neatļauta izmantošana ir aizliegta.