Considerăm un joc bazat pe un dispozitiv ca în imaginea de mai jos:
Dispozitivul constă dintr-o mulţime de platforme orizontale de diferite lungimi, plasate la diferite înălţimi. Platforma cea mai joasă este podeaua (este plasată la înălţimea 0 şi are lungime infinită).
Dintr-o poziţie specificată, este lăsată să cadă o minge, la momentul 0. Mingea cade cu viteză constantă de 1 metru pe secundă. Când mingea ajunge pe o platformă, începe să se rostogolească spre unul din capetele acesteia, la alegerea jucătorului, cu aceeaşi viteză de 1 metru pe secundă. Când mingea ajunge la capătul platformei, îşi continuă căderea liberă, pe verticală. Mingea nu are voie să cadă liber mai mult de MAX metri odată (între două platforme).
Cerinţă
Scrieţi un program care determină un mod de rostogolire a mingii pe platforme astfel încât să ajungă la podea cât mai repede posibil.
Date de intrare
Fişierul de intrare fall.in conţine pe prima linie numerele naturale N X Y MAX, separate prin câte un spaţiu, reprezentând numărul de platforme (excluzând podeaua), poziţia de plecare a mingii (abscisa şi ordonata), şi respectiv distanţa maximă pe care mingea are voie să cadă; platformele sunt numerotate de la 1 la N. Fiecare dintre următoarele N linii conţine trei numere întregi X1 X2 H, separate prin spaţii; numerele de pe cea de a i-a linie dintre cele N semnifică faptul că platforma i este situată la înălţimea H, între coordonatele orizontale X1 şi X2 inclusiv (X1<X2, i=1..N).
Date de ieşire
Fişierul de ieşire fall.out va conţine o singură linie pe care va fi scris un număr întreg T, reprezentând timpul minim în care mingea atinge podeaua.
Restricţii
• 1≤N≤1000
• -20000≤X1, X2≤20000, pentru 1≤i≤N
• 0<H<Y≤20000
• Diametrul mingii şi grosimea platformelor se ignoră. Dacă mingea cade exact pe marginea unei platforme, se consideră că a căzut pe platformă.
• Oricare două platforme nu au puncte comune.
• Pentru datele de test există întotdeauna soluţie.
• Toate dimensiunile sunt exprimate în metri.
