Рекламне оголошення#3901
Івану з дитинства подобались газети. У нього навіть була мрія стати головним редактором газети. Одного разу йому випав шанс здійснити свою мрію. Щоб влаштуватись на роботу у видавництво, йому необхідно виконати тестове завдання — зверстати рекламне оголошення.
Задано поле шириною та висотою . Оголошення повинно складатись з одного або декількох рядків, у яких необхідно розмістити у заданому порядку слів. Про -те слово відомо, що при друку у стандартному масштабі воно займає прямокутник шириною a_i та висотою b_i.
Щоб оголошення виглядало красиво, усі слова у ньому повинні бути надруковані в одному масштабі. При друці у масштабі розміри усіх слів домножуються на . Якщо спочатку слово займало прямокутник a_i \times b_i, то при друці у масштабі воно займає прямокутник розміром (k \cdot a_i) \times (k \cdot b_i). Крім того, якщо у рядку більше одного слова, то усі слова у ньому повинні мати однакову висоту. Зрозуміло, що жодне слово не повинно виходити за границі поля.
На рисунку наведено приклад красивого оголошення з трьома словами.
Допоможіть Івану знайти максимальний масштаб, при якому можна зверстати оголошення, яке задовольняє цим критеріям. Зверніть увагу, що змінювати порядок слів не можна, вони повинні читатись по рядках зверху вниз, зліва направо у тому порядку, у якому задані.
У першому рядку вхідного файлу задано три числа: , та (1 \leq N \leq 100000, 1 \leq W, H \leq 10^9) — кількість слів в оголошенні, ширина та висота оголошення. У наступних рядках задано по два цілих числа, у -му з них задано a_i та b_i (1 \leq a_i, b_i \leq 10^9) — ширина та висота -го слова.
Виведіть одне дійсне число — максимальний масштаб. Відповідь потрібно вивести з абсолютною або відносною похибкою не більше 10^{-9}. Це значить, що якщо правильна відповідь , а ви вивели , то вашу відповідь буде зараховано як вірну, якщо |a - p| \leq 10^{-6}.
Приклад 1