M. Melting
time limit per test
5 s
memory limit per test
1024 megabytes
input
standard input
output
standard output

It's so hot this summer!

Vasya is walking along the street, which can be viewed as an infinite two-dimensional plane. He is currently at the point $$$S = (s_x, s_y)$$$, while an ice cream truck is stationed at the point $$$T = (t_x, t_y)$$$.

Despite his eagerness to get some ice cream, the intense sunshine makes the journey uncomfortable. Fortunately, there are $$$N$$$ shaded areas created by trees and buildings blocking the sun, providing some cooler spots. For the purpose of this problem, these shaded areas are considered as convex polygons.

Vasya aims to find a path to the ice cream truck that minimizes the distance traveled outside these shaded areas. Please determine the minimum length Vasya needs to walk without shade.

Input

The first line is an integer $$$N$$$, denoting the number of shade areas. Then there will be $$$N$$$ sections, each describing a convex polygon.

The $$$i$$$-th section starts with an integer $$$k_i$$$, which is the number of vertices in the $$$i$$$-th shade. Each of the next $$$k_i$$$ lines will be two space-separated integers $$$x_{ij}, y_{ij}$$$, denoting the coordinate of the vertices of the convex polygon. In total, there will be $$$k_i + 1$$$ lines in the $$$i$$$-th section. The vertices will be given in counterclockwise order.

Finally, there will be two lines, each consists of two space-separated integers, $$$s_x, s_y$$$ and $$$t_x, t_y$$$, denoting the coordinate of the starting point and the goal.

  • $$$1 \leq N \leq 500$$$.
  • $$$k_i \geq 3$$$.
  • $$$\sum _ {i=1} ^ N k_i \leq 10^5$$$.
  • $$$-10^9 \leq x_{ij}, y_{ij}, s_x, s_y, t_x, t_y \leq 10^9$$$.
  • Each shade area is guaranteed to be a strict convex polygon. By strict, it means that no three consecutive vertices lie on the same line and no two points coincide. Also, the vertices will be given in counterclockwise order.
Output

Print the desired minimum length.

Your answer will be accepted if the absolute or relative error does not exceed $$$10^{-6}$$$. Formally, let your answer be $$$a$$$, and the jury's answer be $$$b$$$. Your answer is considered correct if $$$\frac{|a-b|}{\max(1,|b|)}\le 10^{-6}$$$.

Examples
Input
3
3
10 10
20 10
20 50
3
30 50
90 50
70 60
3
90 10
100 10
90 60
0 0
100 0
Output
34.14213562373095048677
Input
3
4
-80 0
-70 -20
-50 -25
-60 20
5
70 -40
90 40
70 30
60 20
50 -10
3
-80 -20
100 20
0 20
-100 0
100 0
Output
39.40285000290663788153
Note

The exact answer of sample 1 and sample 2 are $$$20 + 10 \sqrt{2}$$$ and $$$20 + \frac{80}{\sqrt{17}}$$$, respectively.

Illustration of sample 1 and sample 2