Problem Description

The cows are taking a multiple-choice test. In a normal test, your choices for each question are graded separately and then added up, but in this test, your choices are added together first and then graded.

Specifically, you are given $N$ ($2 \le N \le 10^5$) groups of integer vectors on the 2D plane, where each vector is represented by an ordered pair $(x, y)$. Choose one vector from each group so that the sum of the chosen vectors is as far from the origin as possible.

The input guarantees that the total number of vectors does not exceed $2 \times 10^5$. Each group contains at least $2$ vectors, and all vectors within the same group are distinct. The input also guarantees that the absolute value of each $x$ and $y$ coordinate does not exceed $\dfrac{10^9}{N}$.

Input Format

The first line contains $N$, the number of groups of vectors.

For each group, the first line contains $G$, the number of vectors in the group. The next $G$ lines contain the vectors in the group. Adjacent groups are separated by a blank line.

Output Format

Output the maximum possible squared Euclidean distance.

3

2
-2 0
1 0

2
0 -2
0 1

3
-5 -5
5 1
10 10

242

Hint

[Sample Explanation]

The best plan is to choose $(1, 0)$ from the first group, $(0, 1)$ from the second group, and $(10, 10)$ from the third group. The sum of these vectors is $(11, 11)$, and its squared distance from the origin is $11^2 + 11^2 = 242$.

[Constraints]

• In test cases 1-5, the total number of vectors does not exceed $10^3$.
• In test cases 6-9, each group contains exactly $2$ vectors.
• In test cases 10-17, there are no additional restrictions.

Problem provided by: Benjamin Qi.

Translated by ChatGPT 5