Xiao Cong is a warrior.

Xiao Cong has embarked on a journey to save the world.

There are $N$ green onion monsters in front of Xiao Cong.

The green onion monsters are formidable; the $i$-th monster has an attack power of $a_i$ and a defense power of $d_i$.

Xiao Cong has an attack power of $A$ and a defense power of $D$.

The cost for Xiao Cong to defeat the $i$-th green onion monster is $A\cdot d_i+D\cdot a_i$.

The cost for Xiao Cong to defeat multiple green onion monsters is not the sum of the costs to defeat each individual monster, but rather the maximum of those costs.

Xiao Cong now needs to defeat $R$ green onion monsters.

Shen Cong is the god of green onions, and Shen Cong will evaluate Xiao Cong's defeat of the $R$ green onion monsters. Shen Cong's evaluation of Xiao Cong is the cost required to defeat these $R$ green onion monsters divided by the cost required for Xiao Cong to defeat all $N$ green onion monsters with the same attack and defense power.

Since Shen Cong is the god of green onions, after Xiao Cong chooses the $R$ green onion monsters to defeat, Shen Cong will set Xiao Cong's attack and defense power to minimize the evaluation Xiao Cong receives.

Shen Cong does not want this value to be negative, so if the value is negative, Shen Cong will force it to be $0$.

Xiao Cong is a warrior.

Xiao Cong will not give in.

Xiao Cong needs to choose $R$ green onion monsters such that he can receive the highest possible evaluation from Shen Cong.

Xiao Cong wants to find this evaluation value.

Xiao Cong is kind, so he has written out the mathematical representation of the evaluation value for you:

$$\max_{S\subseteq[N],|S|=R}\left[\min_{A,D\in\mathbb{Z}^+}\frac{\max_{i\in R}\left(A\cdot d_i+D\cdot a_i\right)}{\max_{i\in[N]}\left(A\cdot d_i+D\cdot a_i\right)}\right]$$

Input

The test cases contain multiple sets of data.

For each set of data, the first line contains two integers representing $N$ and $R$.

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

Output

For each set of data, output one real number representing the answer. You must ensure that the error between your answer and the standard answer does not exceed $10^{-6}$.

Examples

Input 1

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

Output 1

1.000000
0.600000

Subtasks

$1\leq R\leq N\leq 10^3$, $a_i, d_i$ are all positive integers, the number of data sets does not exceed $50$, and all attack and defense powers are positive integers.