Humanity's Last Code Exam / 2021_K / Take On Meme

## Problem Statement

The Internet can be so fickle. You work for a small ad agency, Mimi’s Mammoth Memes. Your ad campaigns rely on the hope of producing the next hit viral meme. Unfortunately, the last four hundred or so memes have failed to take off. To try a new approach, you decide to crowdsource.

According to your scientific meme theory, all memes can be rated from −∞ to ∞ on two scales: xanthochromism and yellowishness, also known as (x,y) values. The best memes are memorable for being particularly xanthochromic, yellowish, unxanthochromic, or unyellowish. The “quality” of any meme is directly measurable as its squared Euclidean distance (x²+y²) from the Base Meme (0,0), known as All Your Base.

To produce the ultimate viral meme, you’ll be taking your company’s last few failed memes and throwing them into a tournament, represented as a rooted tree. Input memes come in at the leaves, and at each internal node, a vote will be held among its k child memes (x₁,y₁),…,(x_(k),y_(k)). After the vote, all the memes will be merged into a brand new meme, calculated to emphasize the winner and de-emphasize all the losers:

The resultant x value will be:

∑_(i=1)^(k)w_(i)⋅x_(i)

where w_(i) is 1 if the i-th child won, and -1 otherwise. The y value is computed similarly. This new meme will move on to the next vote in the tournament, or if there is no parent, it will be declared the champion and the ultimate meme.

What is the largest possible quality for any meme that the tournament could produce?

## Input

The first line of input contains an integer n (1≤n≤10⁴), giving the total number of nodes in the tournament tree. The next n lines each describe a single tree node indexed from 1 to n. The line for node i starts with an integer k_(i) (0≤k_(i)≤100), the number of children of that node. If k_(i) is 0, then node i is an input meme and there will be two more integers x_(i) and y_(i) (−10³≤x_(i),y_(i)≤10³) describing it. If k_(i)>0, then k_(i) different integers j (i<j≤n) will follow, giving the indices of the k_(i) nodes entering this voting step.

All input memes will eventually be merged into the final output meme at node 1. The complete tree will have a height of no more than 10.

## Output

Output the largest possible quality for the champion meme at node 1.

## Sample Input 1

## Problem Statement

The Internet can be so fickle. You work for a small ad agency, Mimi’s Mammoth Memes. Your ad campaigns rely on the hope of producing the next hit viral meme. Unfortunately, the last four hundred or so memes have failed to take off. To try a new approach, you decide to crowdsource.

According to your scientific meme theory, all memes can be rated from \(-\infty\) to \(\infty\) on two scales: xanthochromism and yellowishness, also known as \((x, y)\) values. The best memes are memorable for being particularly xanthochromic, yellowish, unxanthochromic, or unyellowish. The “quality” of any meme is directly measurable as its squared Euclidean distance \((x^2 + y^2)\) from the Base Meme \((0, 0)\), known as All Your Base.

To produce the ultimate viral meme, you’ll be taking your company’s last few failed memes and throwing them into a tournament, represented as a rooted tree. Input memes come in at the leaves, and at each internal node, a vote will be held among its \(k\) child memes \((x_1, y_1), \ldots, (x_k, y_k)\). After the vote, all the memes will be merged into a brand new meme, calculated to emphasize the winner and de-emphasize all the losers:

The resultant \(x\) value will be:

\[
\sum_{i=1}^{k} w_i \cdot x_i
\]

where \(w_i\) is 1 if the \(i\)-th child won, and -1 otherwise. The \(y\) value is computed similarly. This new meme will move on to the next vote in the tournament, or if there is no parent, it will be declared the champion and the ultimate meme.

What is the largest possible quality for any meme that the tournament could produce?

## Input

The first line of input contains an integer \(n\) \((1 \leq n \leq 10^4)\), giving the total number of nodes in the tournament tree. The next \(n\) lines each describe a single tree node indexed from 1 to \(n\). The line for node \(i\) starts with an integer \(k_i\) \((0 \leq k_i \leq 100)\), the number of children of that node. If \(k_i\) is 0, then node \(i\) is an input meme and there will be two more integers \(x_i\) and \(y_i\) \((-10^3 \leq x_i, y_i \leq 10^3)\) describing it. If \(k_i > 0\), then \(k_i\) different integers \(j\) \((i < j \leq n)\) will follow, giving the indices of the \(k_i\) nodes entering this voting step.

All input memes will eventually be merged into the final output meme at node 1. The complete tree will have a height of no more than 10.

## Output

Output the largest possible quality for the champion meme at node 1.

## Sample Input 1