空间跃迁

题目描述

本题是 空间跃迁 的Normal版本，Normal版本与Easy版本的区别主要在于可启用的加速站数量 $k$ 的限制，在Normal版本中，可启用的加速站数量限制为 $3 \le k \le 10$。通过本题的代码一定可以通过Easy版本。

在你的不懈帮助下，Orange成功研制出了空间跃迁技术。空间跃迁技术利用升维技术，将物体转移到第四维度，在第四维度中将时间线折叠，从而让物体瞬间移动到三维空间的另外一点，且不存在在三维空间的移动过程。

而空间跃迁技术的关键在于如何将物体升到第四维度，Orange研究出了一种方法，只要将物体的速度提升到光速的1919810倍，就可以强行让物体升维。因此Orange研究出了一种特殊的空间轨道加速器，它可以让物体在短时间内将速度提高若干倍，从而实现升维。

Orange的轨道加速器可以看做一个水平的数轴，上面依次排布了 $n$ 个加速站，第 $i$ 个加速站位于 $p_i$ 处，并且具有 $a_i$ 个单位的能量。

加速站两两联立，构成 $n - 1$ 个加速区间，在通过第 $i$ 到第 $i + 1$ 个加速站构成的加速区间时，速度会发生如下改变：

$$v_{i+1} = v_i \times (a_i + a_{i+1}) \div (p_{i+1} - p_i)$$

其中 $v_i$ 表示穿过第 $i$ 个加速站的速度，$v_{i+1}$ 表示穿过第 $i+1$ 个加速站的速度，其他字母如上述题面所述。

物体最开始以 $1$ 个单位的速度穿过第 $1$ 个加速站进入轨道加速器，在经过第 $n$ 个加速站时，物体完成整个加速过程，速度也达到最大化。但是，现在，Orange由于能量短缺，他最多只能启用 $k$ 座加速站，并且其中第 $1$ 座加速站和第 $n$ 座加速站作为轨道加速的关键部分必须启用，你需要帮助Orange决定，启用剩下的哪几个加速站，能够让最后加速后的速度最大，并求出这个最大值。

tips：本题对答案的精度要求非常高，请使用更加优秀的实数类型来计算和存储答案。同时答案保证在正确选择实数类型的情况下能够被表示。且约定最后的答案不会超过 $1.8 \times 10^{19}$。

输入格式

输入包含多组测试数据，第一行为一个整数 $T$，表示测试数据数量。 对于每组测试数据： 第一行为2个整数 $n$ 和 $k$。表示所有加速站的数量和可以启用的加速站数量。 第二行为 $n$ 个整数 $p_i$，表示每个加速站的位置。 第三行为 $n$ 个整数 $a_i$，表示每个加速站的能量。

数据范围

$3 \le k \le 10$ $k \le n \le 2 \times 10^3$ $1 \le a_i \le 10^4$ $1 \le p_i \le 2 \times 10^5$ $p_1 < p_2 < \cdots < p_i < p_{i+1} < \cdots < p_n$ $\sum n \le 2\times 10^3$

输出格式

对于每组测试数据，输出一行，包含一个实数表示答案。

当你的输出答案与正确答案的绝对差小于 $10^{-1}$，将会被认为正确。

样例 #1

样例输入 #1

1
6 5
1 3 5 7 8 10
7 6 9 5 1 3

样例输出 #1

910.0000000000

提示

样例解释1

我们可以选择 $1, 2, 3, 4, 6$ 这 $5$ 个点： 在经过加速站 $1$ 到 $2$ 时：速度变成 $1 \times (7 + 6) / (3 - 1) = 6.5$ 在经过加速站 $2$ 到 $3$ 时：速度变成 $6.5 \times (6 + 9) / (5 - 3) = 48.75$ 在经过加速站 $3$ 到 $4$ 时：速度变成 $48.75 \times (9 + 5) / (7 - 5) = 341.25$ 在经过加速站 $4$ 到 $6$ 时：速度变成 $341.25 \times (5 + 3) / (10 - 7) = 910$ 可以证明这样选择能够获得最大的速度。