Description

KC and SH often went to 85°C in Fuzhou to drink coffee or something else.

One day, KC wanted a cup of coffee. The waiter told him there are $n$ kinds of seasonings, and exactly $m$ of them can be added to this cup of coffee (KC will add exactly $m$ kinds, not fewer). Depending on which seasonings are added, the time needed to make the coffee and the resulting deliciousness will differ.

After learning all $n$ seasonings, as a former chemistry contest ace, KC immediately knows the time cost $c _ i$ and the deliciousness $v _ i$ of each seasoning. Since KC is in a hurry to get back to solving problems, he wants to drink the coffee as soon as possible, but he also wants it to be delicious. So he came up with a plan: he wants to drink the coffee that maximizes $\dfrac{\sum v _ i}{\sum c _ i}$, that is, the deliciousness per unit time.

Now KC tells SH the information about the seasonings and asks SH to compute the $\dfrac{\sum v _ i}{\sum c _ i}$ of the coffee he will drink. But SH does not want to help, so KC turns to you.

Note: $\sum$ denotes summation, so $\dfrac{\sum v _ i}{\sum c _ i}$ means the total deliciousness divided by the total time cost.

Input Format

The input consists of three lines.

• The first line contains two integers $n, m$, the number of seasonings and the number to add.
• The next two lines each contain $n$ integers. In these two lines, the $i$-th integer of the first line is the deliciousness $v _ i$ of seasoning $i$, and the $i$-th integer of the second line is the time cost $c _ i$ of seasoning $i$.

Output Format

Output a real number $T$, the maximum value of $\dfrac{\sum v _ i}{\sum c _ i}$ for KC’s coffee, rounded to three decimal places.

3 2
1 2 3
3 2 1

1.667

Hint

Explanation for Sample 1:

KC chooses seasonings $2$ and $3$, $\dfrac{\sum v _ i}{\sum c _ i} = \dfrac{2 + 3}{2 + 1} = 1.667$.

It can be verified that there is no better choice.

Constraints:

For $20 \%$ of the testdata: $1 \leq n \leq 5$.

For $50 \%$ of the testdata: $1 \leq n \leq 10$.

For $80 \%$ of the testdata: $1 \leq n \leq 50$.

For $100 \%$ of the testdata: $1 \leq n \leq 200, 1 \leq m \leq n, 1 \leq c[i], v[i] \leq 1 \times 10 ^ 4$.

The testdata guarantees that the answer does not exceed $1000$.

Translated by ChatGPT 5