Wyścig

Limit pamięci: 64 MB

Wyścig Tour de Bajtocja jest organizowany co roku na trasie z miasta A do miasta B. Ze względu na dziurę budżetową, w tym roku wyścig odbędzie się tylko na pewnym odcinku trasy. Nie jest jeszcze ustalone, jaki to będzie odcinek, choć ustalona jest już jego długość. Na całej trasie rozstawione są znaki ograniczające prędkość jazdy. Ograniczenie obowiązuje do momentu zmiany tego ograniczenia przez inny znak. Wyścig Tour de Bajtocja znany jest z obowiązku przestrzegania ograniczeń prędkości.

Organizatorzy zastanawiają się, jaki fragment trasy (o długości ) wybrać, aby przestrzegając ograniczeń prędkości, można było go jak najszybciej przejechać.

Zostałeś poproszony o napisanie programu, który wyznaczy najkrótszy czas przejechania takiego fragmentu trasy.

Wejście

W pierwszym wierszu standardowego wejścia znajdują się trzy liczby całkowite , oraz (, ), pooddzielane pojedynczymi odstępami, oznaczające odpowiednio liczbę znaków ustawionych na trasie, długość odcinka, na którym powinien odbyć się wyścig, oraz długość trasy z A do B.

Następne wierszy zawiera opisy kolejnych znaków ustawionych na trasie. Opis znaku składa się z dwóch liczb całkowitych , (, ), oddzielonych pojedynczym odstępem, oznaczających odpowiednio odległość -tego znaku od miasta A oraz ograniczenie prędkości obowiązujące od ustawienia tego znaku. Możesz założyć, że .

W testach wartych przynajmniej 50% punktów zachodzą dodatkowe warunki oraz .

Wyjście

W pierwszym i jedynym wierszu standardowego wyjścia Twój program powinien wypisać jedną liczbę rzeczywistą zaokrągloną do dokładnie trzech cyfr po kropce dziesiętnej, oznaczającą najkrótszy możliwy czas przejechania trasy długości . Wybierany odcinek trasy nie może wykraczać poza trasę z miasta A do miasta B.

Przykład

Dla danych wejściowych:

3 4 7
0 30
2 50
4 40

poprawną odpowiedzią jest:

0.090

Wyjaśnienie do przykładu: Optymalna trasa zaczyna się w odległości od miasta A. Czas przejechania tej trasy jest równy .

Wskazówka: Aby uniknąć błędów zaokrągleń, do obliczeń polecamy używać typów rzeczywistych podwójnej precyzji (double) oraz standardowych procedur/funkcji służących do wypisywania liczb rzeczywistych z zadaną precyzją.

Autor zadania: Jacek Tomasiewicz.