你在《星际争霸 II》中进行人族对神族的对抗，游戏进入了淘汰阶段，可以简化为一维场景。

你拥有一支由 $m$ 架配备了升级版超飞行旋翼的女妖战机（banshee）组成的军队，它们位于坐标轴上的点 $0$ 处。你的对手在坐标轴的正半轴上拥有 $n$ 座建筑。每座建筑都被视为一个线段。

以下是女妖战机的移动规则：

• 配备了升级版超飞行旋翼的女妖战机速度为 $5.25$ 单位/秒。加速度是瞬时的。
• 在《星际争霸》中，飞行单位没有单位碰撞，因此任意数量的女妖战机都可以位于同一点。

接下来是攻击规则：

• 女妖战机可以攻击 $6$ 单位范围内的目标。如果建筑的任意一点在范围内，则该建筑可以被攻击。
• 为简化起见，攻击过程如下：首先，女妖战机必须在不移动的情况下等待 $0.89$ 秒的冷却时间。之后，它会发射立即对目标造成伤害的炮弹。这最接近于射击前的武器充能。请注意，这与实际的《星际争霸》机制不同。
• 在每次攻击中，女妖战机攻击一个目标并同时发射两枚炮弹。每枚炮弹造成 $12$ 点伤害。

最后是防御规则：

• 最初，每座建筑都有满额的生命值（hitpoints）和护盾（shields）。如果建筑的生命值降至 $0$ 或以下，则该建筑被摧毁。
• 如果建筑受到伤害但未被摧毁，且在 $10$ 秒内没有受到进一步伤害，其护盾开始充能。该建筑每秒恢复 $2$ 点护盾，直到护盾回满或再次受到攻击。恢复是连续的：例如，$0.1$ 秒内恢复 $0.2$ 点护盾。
• 假设建筑有 $h$ 点生命值和 $s$ 点护盾，受到 $d$ 点伤害。首先，护盾会吸收尽可能多的伤害：护盾减少 $d' = \min(s, d)$。然后，生命值减少剩余的伤害 $d - d'$。

给定游戏中的初始位置，摧毁所有神族建筑所需的最短时间是多少？

输入格式

输入包含多个测试用例。 第一行包含一个整数 $t$，表示测试用例的数量。接下来是 $t$ 个测试用例，格式如下：

每个测试用例的第一行包含两个整数 $n$ 和 $m$ ($1 \le n \le 2 \cdot 10^5$, $1 \le m \le 10^9$)：剩余神族建筑的数量和你的女妖战机数量。所有女妖战机最初都位于坐标轴的 $0$ 点。

接下来的 $n$ 行，每行包含四个整数 $\ell, r, h, s$ ($0 \le \ell < r \le 10^{12}$, $0 < h \le 10^6$, $0 \le s \le 10^6$)：分别为建筑的左端点、右端点、生命值和护盾值。你可以假设建筑互不重叠，且按 $\ell$ 坐标递增的顺序给出。

所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$。

输出格式

对于每个测试用例，在单独的一行中输出一个数字：摧毁所有神族建筑所需的最短时间。如果你的答案与裁判答案的绝对误差不超过 $10^{-4}$，则视为正确。

样例

输入 1

2
2 1
1 2 1 100
100 500 736 0
3 2
0 1 12 0
1 2 6 6
2 3 3 10

输出 1

49.94476
1.78000