Advertisement#3901
Ivan has always been passionate about newspapers, dreaming of one day becoming an editor-in-chief. When he finally got the opportunity to pursue this dream, he was tasked with a test assignment: designing an advertisement layout.
The advertisement must fit within a rectangular field of width and height . It should consist of words arranged in the given order. Each word has a standard size, occupying a rectangle with width a_i and height b_i.
To ensure the advertisement is visually appealing, all words must be printed at the same scale. At a scale factor of , the dimensions of each word are scaled by . Thus, a word originally occupying a_i \times b_i will, at scale , occupy a rectangle of size (k \cdot a_i) \times (k \cdot b_i). Additionally, if multiple words appear on the same line, they must all share the same height. Importantly, no word should exceed the boundaries of the field.
The illustration below provides an example of a well-designed advertisement featuring three words.
Your task is to help Ivan determine the maximum scale factor that allows the advertisement to be typeset according to these rules. The words must be placed in the specified order, read line by line from top to bottom and left to right.
The first line of the input contains three integers: , , and (1 \leq N \leq 100000, 1 \leq W, H \leq 10^9) — representing the number of words, the width, and the height of the advertisement field, respectively. The following lines each contain two integers a_i and b_i (1 \leq a_i, b_i \leq 10^9) — the width and height of the -th word.
Output a single real number — the maximum scale factor. The result should be accurate to an absolute or relative error of no more than 10^{-9}. This means if the correct answer is , and you provide , your answer will be considered correct if |a - p| \leq 10^{-6}.
Example 1