D. Divided Banner
time limit per test
4 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

The sponsor banner was left outside during the night, and the wind tore it into $$$n$$$ fragments. The banner was cut along its height, so every fragment still has the full height of the original banner, from the bottom edge to the top edge.

Each fragment is a filled convex polygon. Every fragment is contained between the horizontal lines $$$y=0$$$ and $$$y=H$$$, the bottom and the top edge of the banner, and touches both lines.

The volunteers want to hang all the fragments again on the wall behind the scoreboard, and that wall is short. They may hang the fragments in any order and move each fragment to the left or to the right by any real distance. They may not move a fragment up or down, rotate it, or turn it over: every fragment hangs from the same rail, with its bottom edge on the line $$$y=0$$$.

An arrangement is valid if the interiors of every two fragments are disjoint. Their boundaries are allowed to touch, and a fragment hung exactly against its neighbour is what the volunteers want.

The length of an arrangement is the difference between the largest and smallest $$$x$$$-coordinates occupied by any fragment, that is, the piece of wall it needs. Find the minimum possible length of a valid arrangement.

Input

The first line contains two integers $$$n$$$ and $$$H$$$ ($$$1 \le n \le 18$$$, $$$1 \le H \le 10^4$$$) — the number of fragments and their common height.

The description of the $$$n$$$ fragments follows.

For each fragment, the first line contains an integer $$$k_i$$$ ($$$3 \le k_i \le 300$$$) — the number of vertices of the polygon.

Each of the next $$$k_i$$$ lines contains two integers $$$x_{i,j}$$$ and $$$y_{i,j}$$$ ($$$-10^4 \le x_{i,j} \le 10^4$$$, $$$0 \le y_{i,j} \le H$$$) — the coordinates of its $$$j$$$-th vertex.

The vertices of every polygon are given in counterclockwise order. It is guaranteed that:

  • every polygon is convex (not necessarily strictly convex) and has positive area;
  • consecutive vertices on the boundary may be collinear;
  • every polygon has at least one point on $$$y=0$$$ and at least one point on $$$y=H$$$;
  • the sum of $$$k_i$$$ over all fragments does not exceed $$$300$$$.

Coordinates belonging to different fragments are expressed in independent local coordinate systems.

Output

Print one real number — the minimum possible length of a valid arrangement.

Your answer is considered correct if its absolute or relative error does not exceed $$$10^{-6}$$$.

Examples
Input
1 2
4
0 0
3 0
3 2
0 2
Output
3.0000000000
Input
2 2
3
0 0
2 2
0 2
3
0 0
2 0
2 2
Output
2.0000000000
Input
2 4
3
0 0
4 2
0 4
4
0 0
1 0
1 4
0 4
Output
5.0000000000
Note

In the second example, the two triangular fragments can share a slanted boundary, so their projections on the $$$x$$$-axis may completely overlap.

In the third example, the first fragment reaches $$$x=4$$$ halfway up the banner. The rectangular fragment can be placed immediately to its right, touching it at that point, for a total length of $$$5$$$.