P - Plošiny

Časový limit: 2s, Pamäťový limit: 64MiB

Programovacie jazyky: Pascal, C, C++, Java, C++0x, Python 3

Počet bodov: 1

[ Pošli riešenie ] [ Tvoje riešenia ] [ Správne riešenia ] [ Vzorové riešenie ]

Jožkovi spolužiaci sa chceli Jožkovi pomstiť za úlohu ťažisko, tak ho odvliekli a nechali na vrchu rozostavanej budovy. Ďalší spolužiak chcel Jožkovi pomôcť, no nechcel skončiť ako Jožko. Všimol si, že na okraji budovy sú plošiny, po ktorých by Jožko mohol postupne zoskakovať. Keďže Jožko nie je fyzicky zdatný, tak nevie skákať na veľkú vzdialenosť, nechce zoskakovať veľké výšky a tiež nedokáže skákať na vyššiu plošinu.

Úloha

Vytvorte program, ktorý pomôže nájsť Jožkovi cestu dole po plošinách.

Vstup

Prvý riadok obsahuje počet plošín N (2 ≤ N ≤ 10 000) a vzdialenosť skoku D (1 ≤ D ≤ 100).

Nasleduje N riadkov popisujúcich jednotlivé plošiny v tvare: X_L X_R Y, kde X_L je ľavá x-ová súradnica plošiny, X_R je pravá x-ová súradnica plošiny a Y je zvislá vzdialenosť plošiny od vrchu budovy.

Predpokladajte, že:

vždy bude prítomná iba jedna plošina so zvislou vzdialenosťou 0, ktorá je začiatočná pozícia,
Jožko vie sa pohybovať po plošine, na ktorej sa nachádza,
Jožko skočí plošinu v rovnakej výške alebo na nižšiu pošinu iba vtedy, ak v euklidovskej vzdialenosti menšej alebo rovnej D sa nachádza časť plošiny.

Výstup

Výstup pozostáva z dvoch čísel: Y_MAX a N_MAX, kde Y_MAX je zvislá vzdialenosť plošiny najvzdialenejšej od vrchu budovy, kam sa vie Jožko dostať a N_MAX je najmenší počet skokov, ktoré potrebuje vykonať, aby sa dostal na danú plošinu.

Príklad

Vstup:

Výstup:

6 2

16 Finále 1