F. Thesis Group Selection
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
"In IUT, CGPA matters!"

It is almost the end of the 3-1 semester for batch 22, and before the Eid holidays, $$$N$$$ students must be assigned to research groups for their upcoming thesis. There are $$$K$$$ distinct research groups available, and the university has decided on a unique procedure to assign students to these groups based on their academic standing.

Each student has a Face–Value in the department and a CGPA (ranging from 0.00 to 4.00). The assignment process works as follows:

  1. All students are first sorted by their CGPA in descending order. (If multiple students have the exact same CGPA, they are sorted by their Face Value in descending order).
  2. The students are then processed in batches of size $$$K$$$, strictly following this sorted order:
    • The first $$$K$$$ students are randomly and uniformly assigned to $$$K$$$ distinct groups.
    • The next $$$K$$$ students are then randomly and uniformly assigned to $$$K$$$ distinct groups, and this process repeats.
    • The final batch may contain fewer than $$$K$$$ students. If so, they are still randomly and uniformly assigned to distinct groups (meaning no two students from this final batch will end up in the same group).
  3. A research group's score is the average of the CGPAs of all the students assigned to it.

Labib is one of these students. His information is always provided as the first entry in the university's records. He is curious about his academic future and wants to know: what is the expected score of the research group he will eventually be placed in?

Note: The expected value (or expectation) of a random variable is the probability-weighted average of all its possible values. Formally, if a random variable $$$X$$$ can take values $$$x_1, x_2, \dots, x_m$$$ with probabilities $$$p_1, p_2, \dots, p_m$$$ respectively, then its expected value $$$E[X]$$$ is defined as: $$$$$$E[X] = \sum_{i=1}^{m} x_i \cdot p_i$$$$$$

Input

The first line of the input contains a single integer $$$t$$$ ($$$1 \le t \le 10000$$$) — the number of test cases.

The first line of each test case contains two integers $$$N$$$ and $$$K$$$ ($$$1 \le K \le N \le 10^5$$$) — the number of students and the number of research groups.

The second line contains $$$N$$$ integers $$$F_1, F_2, \dots, F_N$$$ ($$$1 \le F_i \le 10^9$$$) — the Face Values of the students. All $$$F_i$$$ are distinct.

The third line contains $$$N$$$ real numbers $$$C_1, C_2, \dots, C_N$$$ ($$$0.00 \le C_i \le 4.00$$$) — the CGPAs of the students. Each $$$C_i$$$ has exactly two digits after the decimal point.

Note: Labib is always the first student in the input, i.e., his Face Value is $$$F_1$$$ and his CGPA is $$$C_1$$$.

It is guaranteed that the sum of $$$N$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output

For each test case, output a single real number — the expected score of Labib's research group.

Your answer will be considered correct if its absolute or relative error does not exceed $$$10^{-6}$$$.

Example
Input
2
4 2
1 2 3 4
3.00 4.00 4.00 3.00
3 1
124 220 217
3.90 3.97 3.88
Output
3.500000000
3.916666667
Note

Explanation of the first case:

Let $$$S_i$$$ denote the $$$i$$$-th student in the input. Labib is $$$\mathbf{S}_1$$$. After sorting, the order is: $$$S_3(4.00, 3) \to S_2(4.00, 2) \to S_4(3.00, 4) \to \mathbf{S}_1(3.00, 1)$$$.

With $$$N=4$$$ students and $$$K=2$$$ groups, each group receives exactly 2 students. The assignment batches are Batch 1 ($$$S_3, S_2$$$) and Batch 2 ($$$S_4, \mathbf{S}_1$$$). Because each batch is split uniformly across the 2 groups, Labib ($$$\mathbf{S}_1$$$) will be paired with exactly one random student from Batch 1.

$$$$$$ \begin{array}{|c|c|c|c|} \hline \textbf{Batch 1 Teammate} & \textbf{Labib (Batch 2)} & \textbf{Group Score} & \textbf{Prob.} \\ \hline S_3 \text{ (4.00)} & S_1 \text{ (3.00)} & (4.00 + 3.00) / 2 = 3.50 & 1/2 \\ \hline S_2 \text{ (4.00)} & S_1 \text{ (3.00)} & (4.00 + 3.00) / 2 = 3.50 & 1/2 \\ \hline \end{array} $$$$$$

$$$$$$\text{Expected Score} = \left(3.50 \times \frac{1}{2}\right) + \left(3.50 \times \frac{1}{2}\right) = 3.50$$$$$$