Maximizing Line Coverage with a Translated Polygon

Xiaofu loves geometry. One day, he drew n straight lines on a white paper and cut out a small paper piece in the shape of a simple m-sided polygon. He wants to translate (i.e. shift without rotation or reflection) the polygon on the paper so that the total length of the portions of the lines covered by the polygon is maximized. Note that if a segment of a line exactly coincides with one of the polygon’s edges, that segment is considered as covered.

Suppose each line is given by the equation \[ a\,x + b\,y + c = 0,\] and the polygon is described by its m vertices given in order (either clockwise or counterclockwise). Your task is to find the translation (i.e. a displacement vector) of the polygon which maximizes the total length of the parts of the lines covered by the polygon. Output the maximum total covered length.

Note: The polygon can be arbitrary (simple polygon, not self–intersecting) and only translation (shifting) is allowed (no rotation or reflection). The answer is considered correct if it has an absolute or relative error of at most 10^-6.

inputFormat

The first line contains two integers n and m (1 ≤ n, m ≤ 50), indicating the number of lines and the number of vertices of the polygon respectively.

The next n lines each contain three real numbers a b c (|a|+|b| > 0), describing a line by the equation:

[ a,x + b,y + c = 0. ]

The following m lines each contain two real numbers, representing the coordinates of the vertices of the polygon in order (the polygon is simple, i.e. non self–intersecting).

outputFormat

Output a single real number – the maximum total length of line segments covered by the polygon after an optimal translation. The answer should be printed with at least 6 decimal places.

sample

1 3
1 0 -1
0 0
0 1
1 0

1.000000