8585번 - Wyścig 다국어

문제

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 $m$) 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.

입력

W pierwszym wierszu standardowego wejścia znajdują się trzy liczby całkowite $n,ドル $m$ oraz $d$ (1ドル ≤ n ≤ 1,000円,000円,ドル 1ドル ≤ m ≤ d ≤ 10^9$), 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 $n$ wierszy zawiera opisy kolejnych znaków ustawionych na trasie. Opis znaku składa się z dwóch liczb całkowitych $s_i,ドル $v_i$ (0ドル ≤ s_i ≤ d,ドル 1ドル ≤ v_i ≤ 1,000円,000円$), oddzielonych pojedynczym odstępem, oznaczających odpowiednio odległość $i$-tego znaku od miasta A oraz ograniczenie prędkości obowiązujące od ustawienia tego znaku. Możesz założyć, że 0ドル = s_1 < s_2 < \dots < s_n$.

출력

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 $m$. Wybierany odcinek trasy nie może wykraczać poza trasę z miasta A do miasta B.

제한

힌트

Wyjaśnienie do przykładu: Optymalna trasa zaczyna się w odległości 2ドル$ od miasta A. Czas przejechania tej trasy jest równy $\frac{2}{50} + \frac{2}{40} = \frac{9}{100}$.

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ą.