Description

Xiaocong is a warrior.

Xiaocong sets out on a journey to save the world.

There are $N$ scallion monsters in front of Xiaocong.

The scallion monsters are powerful. For the $i$-th scallion monster, its attack is $a_i$ and its defense is $d_i$.

Xiaocong's attack is $A$ and its defense is $D$.

The cost for Xiaocong to defeat the $i$-th scallion monster is $A\times d_i + D\times a_i$.

The cost for Xiaocong to defeat many scallion monsters is not the sum of the costs to defeat each one, but the maximum value.

Xiaocong now needs to defeat $R$ scallion monsters.

God-Scallion is the god of scallions. God-Scallion will evaluate Xiaocong for defeating $R$ scallion monsters. The evaluation is defined as the cost needed for Xiaocong to defeat these $R$ scallion monsters divided by the cost for Xiaocong, with the same attack and defense, to defeat all $N$ scallion monsters.

Since God-Scallion is the god of scallions, after Xiaocong selects the $R$ scallion monsters to be defeated, God-Scallion will set Xiaocong's attack and defense to make this evaluation as small as possible.

God-Scallion does not want this value to be negative, so if it is negative, God-Scallion will forcibly change it to $0$.

Xiaocong is a warrior.

Xiaocong will not give in.

Xiaocong needs to choose $R$ scallion monsters so that the evaluation he can obtain from God-Scallion is as large as possible.

Find this evaluation value.

Xiaocong is very kind, so he wrote the mathematical expression of the evaluation value for you:

$$\max_{S\subseteq [N],|S|=R}\Big\lbrack\min_{A,D\in\Z^+}\dfrac{\max_{i\in S}(A\times d_i+D\times a_i)}{\max_{i\in [N]}(A\times d_i+D\times a_i)}\Big\rbrack$$

Input Format

The testdata contains multiple test cases.

For each test case, the first line contains two integers $N, R$.

The next $N$ lines each contain two real numbers, representing $a_i, d_i$ respectively.

Output Format

For each test case, output one real number per line as the answer. You need to ensure that the absolute error between your answer and the standard answer does not exceed $10^{-6}$.

3 3
1 3
2 5
2 3
5 1
1 5
2 4
3 3
4 2
5 1

1.000000
0.600000

Hint

Constraints: $1\le R\le N\le 10^3$, $a_i, d_i$ are both positive integers. The number of test cases does not exceed $50$. All attack and defense values are positive integers.

Copyright Information

From THUPC (THU Programming Contest) 2017.

Translated by ChatGPT 5