Maximizing the Sum Vector Magnitude

You are given N groups of integer vectors on a 2D plane. In each group, there are at least two distinct vectors. Each vector is represented by an ordered pair \( (x,y) \) (with \( |x|,|y| \le \frac{10^9}{N} \)). You must choose exactly one vector from each group. Let \( S_x \) and \( S_y \) be the sum of the \( x \) and \( y \) coordinates respectively of the chosen vectors. Your goal is to maximize the Euclidean distance from the origin of the sum vector, i.e. to maximize

[ D = \sqrt{\Bigl(\sum_{i=1}^{N} x_i\Bigr)^2 + \Bigl(\sum_{i=1}^{N} y_i\Bigr)^2} \quad\text{, equivalently maximize } ; \Bigl(\sum_{i=1}^{N} x_i\Bigr)^2 + \Bigl(\sum_{i=1}^{N} y_i\Bigr)^2. ]

Note: Although the problem’s constraints allow a large number of groups, the actual test cases will be small so that an exact solution can be computed by exploring all combinations.

inputFormat

The input begins with a single integer \( N \) (\(2 \le N \le 10^5\)) on the first line, representing the number of groups. Then for each group, there is a line starting with an integer \( M \) (\( M \ge 2 \)), the number of vectors in that group, followed by \( M \) pairs of integers. Each pair represents the coordinates \( x \) and \( y \) of a vector. It is guaranteed that the total number of vectors does not exceed \(2 \times 10^5\), and within each group the vectors are distinct.

For example, a group line might look like:

2 3 4 -10 -10

outputFormat

Output a single integer: the maximum possible value of \(\Bigl(\sum_{i=1}^{N} x_i\Bigr)^2 + \Bigl(\sum_{i=1}^{N} y_i\Bigr)^2\) that can be achieved by choosing one vector from each group.

sample

2
2 3 4 -10 -10
2 3 4 10 10

365