Maximizing God Onion’s Evaluation

Little Onion is a brave warrior embarking on a journey to save the world. In his path lie N monstrous green onions. The i-th monster has an attack value \(a_i\) and a defense value \(d_i\). Little Onion himself has an attack \(A\) and a defense \(D\). To defeat the i-th monster, the cost incurred is \(A\times d_i + D\times a_i\).

When fighting a group of monsters, the overall cost is not the sum of individual costs but rather the maximum cost among them. That is, if Little Onion chooses a subset \(S\) of monsters, his battle cost (with given \(A,D\)) is

\[ \max_{i\in S} (A\times d_i + D\times a_i). \]

Little Onion must defeat exactly \(R\) monsters. However, the divine God Onion will evaluate his performance by comparing the cost to defeat the chosen \(R\) monsters to the cost of defeating all \(N\) monsters. Their evaluation (for a given \(A,D\)) is

\[ \frac{\max_{i\in S}(A\times d_i + D\times a_i)}{\max_{i\in [N]}(A\times d_i + D\times a_i)}. \]

After Little Onion chooses the \(R\) monsters (i.e. the set \(S\)), God Onion, being capricious, sets \(A\) and \(D\) (which must be positive integers) so as to minimize this ratio. (If the value becomes negative, God Onion forces it to 0, but note that all costs are nonnegative.)

Little Onion, proud and unyielding, wants to choose a set \(S\) of \(R\) monsters so as to maximize the evaluation value he obtains from God Onion. In other words, his final evaluation is mathematically defined as

\[ \max_{S\subseteq [N],|S|=R}\Biggl[\min_{A,D\in\mathbb{Z}^+}\frac{\max_{i\in S}(A\times d_i+D\times a_i)}{\max_{i\in [N]}(A\times d_i+D\times a_i)}\Biggr]. \]

After some investigation it turns out that the optimal evaluation can be computed very simply. Observe that by choosing \(A\) and \(D\) to skew the battle they can force the ratio arbitrarily close to either

\[ \frac{\max_{i\in S} d_i}{\max_{i\in [N]} d_i}\quad\text{or}\quad \frac{\max_{i\in S} a_i}{\max_{i\in [N]} a_i}, \]

and hence the optimal evaluation value is:

• If \(R \ge 2\), Little Onion can always select two monsters (one with the maximum \(d_i\) and one with the maximum \(a_i\)) so as to guarantee an evaluation of 1.
• If \(R = 1\), he must choose a single monster \(i\) and his evaluation becomes \(\min\bigl(\frac{d_i}{\max_{j}\,d_j}, \frac{a_i}{\max_{j}\,a_j}\bigr)\). Thus, his best achievable evaluation is
  \(\max_{1\le i\le N} \min\Bigl(\frac{d_i}{\max_{j} d_j},\;\frac{a_i}{\max_{j} a_j}\Bigr)\).

Your task is to compute this evaluation value given \(N\), \(R\), and the arrays \(\{a_i\}\) and \(\{d_i\}\). Output the value as a floating–point number. It is guaranteed that when \(R \ge 2\) the answer is exactly 1, and when \(R=1\), output the maximum possible value computed as above (typically less than 1 unless a monster achieves both global maximums).

inputFormat

The first line contains two integers \(N\) and \(R\) (1 \(\le\) \(R\) \(\le\) \(N\) \(\le\) 10⁵), representing the number of monsters and the number of monsters Little Onion must defeat.

Each of the next \(N\) lines contains two positive integers \(a_i\) and \(d_i\) (each \(\le 10^9\)), representing the attack and defense values of the \(i\)-th monster respectively.

Note: In the battle cost formula the cost to defeat monster \(i\) is \(A\times d_i + D\times a_i\).

outputFormat

Output a single floating–point number: the maximum evaluation value Little Onion can guarantee, according to the analysis above.

It is acceptable if the output has a small absolute or relative error.

sample

2 1
1 100
100 1

0.01

</p>