19795번 - Рекламное объявление 스페셜 저지다국어

Ивану с детства нравились газеты. У него даже была мечта стать главным редактором газеты. Однажды ему представился шанс осуществить свою мечту. Чтобы устроиться на работу в издательство, ему необходимо выполнить тестовое задание --- сверстать рекламное объявление.

Задано поле шириной $W$ и высотой $H$. Объявление должно состоять из одной или нескольких строк, в которых необходимо разместить в заданном порядке $N$ слов. Про $i$-е слово известно, что при печати в стандартном масштабе оно занимает прямоугольник шириной $a_i$ и высотой $b_i$.

Чтобы объявление выглядело красиво, все слова в нем должны быть напечатаны в одном масштабе. При печати в масштабе $k$ размеры всех слов умножаются на $k$. Если исходно слово занимало прямоугольник $a_i \times b_i$, то при печати в масштабе $k$ оно занимает прямоугольник размером $(k \cdot a_i)\times(k \cdot b_i)$. Кроме того, если в строке более одного слова, то все слова в ней должны иметь одинаковую высоту. Разумеется, ни одно слово не должно выходить за границы поля.

На рисунке приведен пример красивого объявления с тремя словами.

Помогите Ивану найти максимальный масштаб, при котором можно сверстать объявление, которое удовлетворяет этим критериям. Обратите внимание, что менять порядок слов нельзя, они должны читаться по строкам сверху вниз, слева направо в том порядке, в котором заданы.

В первой строке входного файла дано три числа: $N$, $W$ и $H$ ($1 \le N \le 100\,000$, $1 \le W, H \le 10^9$) --- число слов в объявлении, длина и высота объявления. В следующих $N$ строках дано по два целых числа, в $i$-й из них заданы $a_i$ и $b_i$ ($1 \le a_i, b_i \le 10^9$) --- ширина и высота $i$-го слова.

Выведите одно вещественное число $k$ --- максимальный масштаб. Ответ требуется вывести с абсолютной или относительной погрешностью не более $10^{-9}$. Это значит, что если правильный ответ $a$, а вы вывели $p$, то ваш ответ будет засчитан как правильный, если $\frac{|a-p|}{\max(|a|, 1)} \le 10^{-6}$.