Rikka 买了一个新衣柜。这个衣柜的门安装在 $N$ 层：如果我们观察衣柜，可以看到第一扇门在最前面，第二扇门隐藏在它后面，以此类推，直到最后一扇第 $N$ 扇门。

众所周知，Rikka 现在很擅长数学，所以她更容易将这些门想象成位于同一个欧几里得平面上。

每扇门由一对滑动部件组成。考虑一扇门，我们可以假设门的部分是由某条直线 $L$ 分隔的两个半平面。注意，衣柜的设计使得直线 $L$ 不一定是垂直的。

此外，在直线 $L$ 上的某一点放置了两个把手，门的两部分各有一个把手。Rikka 可以抓住一个把手并沿垂直于 $L$ 的方向拉动它，从而将门的相应一半沿该方向移动。Rikka 可以独立地拉动同一扇门两个部分上的把手。

为了打开衣柜，Rikka 依次从第 1 扇门到第 $N$ 扇门打开所有的门。在 Rikka 开始打开下一扇门后，之前所有门的滑动部件就不能再移动了。Rikka 只有在把手在整个移动过程中不被之前的门阻挡时，才能拉动它。因此，如果 Rikka 没有把某扇门打开得足够宽，它可能会在未来阻挡某些后续门的开启。

Rikka 想从她的衣柜里取出 $M$ 个小物品。每个物品都可以表示为平面上给定坐标的一个点。她想打开这些门，使得没有任何物品被任何门阻挡。

作为一名数学家，Rikka 想要最小化她移动把手的总距离。请帮助她计算这个最小值。

输入格式

输入的第一行包含两个整数 $N$ 和 $M$ —— 分别是门的数量和物品的数量 ($1 \le N \le 10^5$, $3 \le M \le 10^5$)。

接下来 $N$ 行，按从第一扇门（表面的门）到第 $N$ 扇门（最里面的门）的顺序描述这些门。每扇门由四个实数描述，小数点后不超过 15 位。这些数字是把手在门关闭时所在点 $H$ 的坐标 $x_h$ 和 $y_h$，以及向量 $D$ 的坐标 $x_d$ 和 $y_d$，使得将门分成两半的直线 $L$ 包含点 $H$ 且垂直于向量 $D$。

接下来 $M$ 行，包含物品的描述。每个物品由其坐标 $x$ 和 $y$ 描述 —— 两个实数，小数点后不超过 15 位。

坐标的绝对值不超过 10。每扇门的向量 $D$ 的长度不小于 $\frac{1}{10}$。你可以假设有三个不共线的物品。

注意，测试数据生成的过程中没有退化情况（例如所有点过于接近而共线等），因此测试数据不旨在造成数值稳定性问题。

输出格式

输出把手移动向量长度之和的最小值。如果答案与最优解的绝对误差或相对误差不超过 $10^{-10}$，则认为答案正确。

样例

输入 1

3 4
-3 3 0.6 -0.3
4 -1 1 1
1 -4 1 0
-2 3
2 3
2 -2
-0.5 -2

输出 1

20.27523290755122432

说明

样例中有三扇门，门分别用红色、绿色和蓝色标记。对于每扇门，实线表示把手移动的轨迹，虚线表示门被移动时两半的位置。黑色十字表示物品。