Guests from Tau Ceti
The organizers of the Vekua Cup were taken aback when they received an application from a team from Tau Ceti. Despite the surprise, the application adhered to all the rules, so the Tau Cetians were accepted into the competition. They planned to arrive in Batumi using their spaceship. To communicate with the approaching ship, the Tau Cetians proposed installing a stationary laser and using a Morse code-like system.
However, on the day of their arrival, an unexpected issue arose: dense clouds appeared, moving over the installation site and obstructing the laser beam. To address the potential errors caused by these clouds, the Tau Cetians urgently requested information from the competition jury: what is the maximum number of times the laser beam could be blocked? Unfortunately, the jury was unaware of the laser's exact location, as this was the organizing committee's responsibility. The weather forecast only indicated that the wind would blow at a constant speed. However, the jury could determine the clouds' positions in the sky. Thus, it was decided to calculate the maximum number of blockages for all possible laser placements and wind directions. Your task is to write a program that computes this number.
To simplify the problem, assume the earth's surface is flat, and each cloud's projection onto the ground is represented as a polygon with integer vertices. All projections are non-overlapping, and the wind, blowing at a constant speed, shifts all clouds along a vector parallel to the earth's surface. The laser is represented as a point on the plane. A cloud blocks the laser if the point representing it lies on the boundary or inside the cloud's projection.
Input
The first line of the input contains the number n - the number of clouds in the sky. The following n lines describe the projections of the individual clouds: the i-th line starts with the number n_i > 3, representing the vertices in the polygon defining the i-th cloud, followed by 2n_i coordinates of these vertices -10^9 ≤ x_i, y_i ≤ 10^9. The total number of vertices across all cloud polygons does not exceed 2000.
Output
Output a single number k - the maximum number of times the laser visibility is interrupted by the clouds.
In the example provided, the maximum number of interruptions, 3, is achieved by placing the laser at the point (0, 4) and directing the wind along the vector [-1, 0].