题目描述

一条大道共有从北到南和从南到北两个方向，记作方向 $1$ 和方向 $2$。

每个方向都各有一条基础车道，除此之外，大道还有 $n$ 条动态车道。

一天共会经过 $m$ 个时刻，编号为 $1 \sim m$，其中第 $i$ 个时刻 $j$ 方向会有 $c_{i, j}$ 辆车驶过。

在每一个时刻 $i$，每一条动态车道 $j$ 都会有 $3$ 种情况，记为 $t_{i, j}$（$t_{i, j}\in \{0, 1, 2\}$）。
其中若 $t_{i, j} = 0$ 则代表这条动态车道无法通行，否则其值就代表这条动态车道允许通过的方向。

动态车道不能随意调转方向，有一个值 $C$ 代表调换动态车道的方向所需要的时间。
具体来说，如果在 $x$ 时刻与 $x + 1$ 时刻之间决定调换动态车道 $j$（$t_{x, j} \ne 0$）的方向。
那么对于 $y \in [x + 1, x + C]$，有 $t_{y, j} = 0$。从 $x + C + 1$ 时刻开始（到下一次调转方向为止），$t_{*, j}$ 才变为 $3 - t_{x, j}$。

特殊的是，对于 $1$ 时刻，可以直接为每个动态车道分配好其对应的方向。

定义时刻 $i$ 时方向 $j$ 的负载量 $v_{i, j}$ 是该时刻通过这个方向的车辆数量与能够通过的车道数量（包括基础和动态车道）的比值，即 $v_{i, j} = \frac{c_{i, j}}{1 + \sum_{k = 1}^n [t_{i, k} = j]}$。

你需要求出在合理的调配下，最大负载量的最小值是多少。

输入格式

本题有多组测试数据。

第一行，一个正整数 $T$，表示测试数据组数。对于每组测试数据：

• 第一行，三个正整数 $n, m, C$。
• 第二行，$m$ 个正整数 $c_{1, 1}, \ldots, c_{m, 1}$，表示在每个时刻通过方向 $1$ 的车辆数量。
• 第三行，$m$ 个正整数 $c_{1, 2}, \ldots, c_{m, 2}$，表示在每个时刻通过方向 $2$ 的车辆数量。

输出格式

对于每组测试数据，一行，一个小数，表示最大负载量的最小值。

本题使用自定义校验器，你的答案与正确答案的绝对误差或相对误差在 $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

提示

【样例解释】

对于样例的第一组测试数据：令 $t_{1, 1} = 2, t_{2, 1} = 0, t_{3, 1} = 1$，这样有 $v_{1, 1} = v_{1, 2} = v_{2, 1} = v_{2, 2} = v_{3, 2} = 1, v_{3, 1} = 1.5$，最大负载量为 $1.5$。可以证明没有比 $1.5$ 更优的分配。

【数据范围】

本题使用捆绑测试。

对于所有数据：$1\leq T\leq10^4$，$1\le n\le 10^5$，$1\le c_{i, 1}, c_{i, 2}\le 10^5$，$1\le C < m\leq5\times10^5$，$\sum m\le 5\times 10^5$。