Żabka Bajtozja
Limit pamięci: 32 MB
Żabka Bajtozja siedzi sobie na jednym z kamieni wystających ponad
powierzchnię stawu i chce wskoczyć do wody.
Jednak nie jest jej obojętne, w jakim miejscu to uczyni.
Otóż chciałaby zanurzyć się możliwie jak najdalej od miejsca,
w którym się w tym momencie znajduje.
Żabka jest jednak świadoma, że długość skoku, jaki może wykonać, jest
ograniczona.
Tak więc największa odległość, w jakiej mogłaby wskoczyć wody, byłaby
równa właśnie długości jej najdłuższego skoku,
gdyby nie wystające z wody kamienie.
Bajtozja wpadła na pomysł, że może skakać po kamieniach, w ten sposób
oddalić się i wskoczyć do wody w miejscu bardziej oddalonym
od swojej początkowej pozycji.
Pomóż jej i napisz program, który policzy, jak daleko od swojego aktualnego
położenia żabka może się zanurzyć.
Zadanie
Napisz program, który:
-
wczyta ze standardowego wejścia opis położeń kamieni wystających
ponad powierzchnię wody, umiejscowienie kamienia, na którym siedzi
Bajtozja oraz długość maksymalnego skoku, jaki jest ona w stanie
wykonać,
-
wyznaczy największą odległość, jaką żabka może przebyć z miejsca,
w którym aktualnie siedzi, do miejsca, w którym zanurzy się pod wodę,
-
wypisze wynik na standardowe wyjście.
Wejście
W pierwszym wierszu wejścia znajdują się trzy liczby całkowite ,
oraz (, , ),
pooddzielane pojedynczymi odstępami
i oznaczające odpowiednio: liczbę kamieni wystających ze stawu, numer kamienia,
na którym siedzi Bajtozja oraz maksymalną długość skoku, jaki może ona wykonać,
podaną w bajtymetrach.
W każdym z kolejnych wierszy znajdują się dwie liczby całkowite
oraz (
dla ), oddzielone pojedynczym odstępem i
oznaczające współrzędne w bajtymetrach -tego
wystającego ze stawu kamienia.
Wyjście
Twój program powinien wypisać w pierwszym i jedynym wierszu wyjścia jedną
liczbę, oznaczającą maksymalną odległość w bajtymetrach miejsca,
w którym Bajtozja może się zanurzyć, od miejsca, w którym
początkowo siedzi. Odległość tę należy wypisać z trzema cyframi
po przecinku. Wypisana wartość może się różnić od dokładnej
o co najwyżej .
Przykład
Dla danych wejściowych:
7 6 3
-3 0
2 1
2 -1
-6 -3
4 0
0 0
3 -1
poprawną odpowiedzią jest:
7.000
Autor zadania: Marian M. Kędzierski.