Problem Description

$\text{Mr. Potato}$ opened two new shops to sell potatoes. He bought $N$ bags of potatoes. The $i$-th bag costs $c_i$ and contains $a_i$ potatoes. He plans to distribute all $N$ bags between the two shops, bag by bag.

In each shop, the average price of potatoes equals the total cost of all bags in that shop divided by the total number of potatoes in that shop. (Note that it is the number of potatoes, not the number of bags.)

Let $P_1$ be the average potato price in the first shop, and $P_2$ be the average potato price in the second shop. $\text{Mr. Potato}$ wants to minimize $P_1 \times P_2$, under the condition that in at least one shop, the number of bags is exactly $L$.

Input Format

The first line contains two integers $N$ and $L$.

The second line contains $N$ integers $a_i$.

The third line contains $N$ integers $c_i$.

Output Format

Output one floating-point number on the first line: the minimum value of $P_1 \times P_2$, rounded to three digits after the decimal point.

3 1
3 2 1
1 2 3

0.556

3 2
2 2 2
3 3 3

2.250

Hint

Constraints

For $30\%$ of the testdata, $2 \le N \le 20$.

For $100\%$ of the testdata, $2 \le N \le 100$, $1 \le L < N$, $1 \le a_i \le 100$, $1 \le c_i \le 10^6$, $\sum\limits_{i=1}^{N} a_i \le 500$.

Source

Translated from COCI 2015-2016 CONTEST #6 T5 KRUMPIRKO.

The score of this problem follows the original COCI setting, with a full score of $140$.

Translated by ChatGPT 5