Description

A main road has two directions: from north to south and from south to north, denoted as direction $1$ and direction $2$, respectively.

Each direction has one base lane. Additionally, the road has $n$ dynamic lanes.

A day consists of $m$ moments, numbered from $1$ to $m$, where at the $i$-th moment, $c_{i, j}$ cars pass through direction $j$.

At each moment $i$, each dynamic lane $j$ can be in one of three states, denoted as $t_{i, j}$ ($t_{i, j} \in \{0, 1, 2\}$).
If $t_{i, j} = 0$, it means the dynamic lane is impassable. Otherwise, its value indicates the direction allowed for passage.

The direction of dynamic lanes cannot be freely switched. A parameter $C$ represents the time required to switch the direction of a dynamic lane.
Specifically, if the direction of dynamic lane $j$ is decided to switch between moment $x$ and $x + 1$ (where $t_{x, j} \ne 0$),
then for $y \in [x + 1, x + C]$, $t_{y, j} = 0$. Starting from moment $x + C + 1$ (until the next switch), $t_{*, j}$ becomes $3 - t_{x, j}$.

As a special case, for the first moment ($1$), the direction of each dynamic lane can be directly assigned.

Define the load $v_{i, j}$ of direction $j$ at moment $i$ as the ratio of the number of cars passing through this direction to the number of available lanes (including the base lane and dynamic lanes), i.e., $v_{i, j} = \frac{c_{i, j}}{1 + \sum_{k = 1}^n [t_{i, k} = j]}$.

Your task is to determine the minimum possible maximum load under a reasonable allocation scheme.

Input Format

There are multiple test cases in this problem.

The first line contains a positive integer $T$, the number of test cases. For each test case:

• The first line contains three positive integers $n, m, C$.
• The second line contains $m$ positive integers $c_{1, 1}, \ldots, c_{m, 1}$, representing the number of cars passing through direction $1$ at each moment.
• The third line contains $m$ positive integers $c_{1, 2}, \ldots, c_{m, 2}$, representing the number of cars passing through direction $2$ at each moment.

Output Format

For each test case, output a single line with a decimal number, representing the minimum possible maximum load.

This problem uses a custom checker. Your answer will be considered correct if its absolute or relative error compared to the correct answer is within $10^{-6}$.

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

1.5000000000
2.0000000000
1.5000000000
3.0000000000

Hint

【Sample Explanation】

For the first test case in the sample: Let $t_{1, 1} = 2$, $t_{2, 1} = 0$, and $t_{3, 1} = 1$. Then, $v_{1, 1} = v_{1, 2} = v_{2, 1} = v_{2, 2} = v_{3, 2} = 1$, and $v_{3, 1} = 1.5$. The maximum load is $1.5$. It can be proven that no allocation yields a better result than $1.5$.

【Data Range】

This problem uses bundled testing.

For all data:
$1 \leq T \leq 10^4$,
$1 \le n \le 10^5$,
$1 \le c_{i, 1}, c_{i, 2} \le 10^5$,
$1 \le C < m \leq 5 \times 10^5$,
$\sum m \le 5 \times 10^5$.

Translated by DeepSeek V3.