P13010 【MX-X13-T5】"In the Vast Sea of People Like the Evening Rush Hour in the City"

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.

**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.

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}$.

**【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.** | Subtask ID | Points | $n\leq$ | $C\leq$ | $\sum m\leq$ | |:--:|:--:|:--:|:--:|:--:| | $1$ | $15$ | $1$ | $m-1$ | $5\times10^5$ | | $2$ | $20$ | $10^5$ | $1$ | $5\times10^5$ | | $3$ | $15$ | $10^5$ | $m-1$ | $100$ | | $4$ | $20$ | $10^5$ | $m-1$ | $5\times10^4$ | | $5$ | $30$ | $10^5$ | $m-1$ | $5\times10^5$ | 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.