Maximizing Combat Power in Neverland

In Neverland, a magical world, islands are arranged in a circular fashion. Each island is inhabited by unique creatures who share a peculiar friendship property: for any two distinct creatures a and b on the same island, there exists exactly one creature c such that c is a friend of both a and b. (In some islands there may be only one creature living in solitude.) This forces the island (if it has more than one creature) to have a friendship graph structure known as a windmill graph. In a windmill graph with m=2k+1 vertices, one vertex (the center, also the island's representative) is adjacent to all other vertices, and the remaining vertices form k disjoint pairs with an edge joining the pair.

Moreover, each island selects its most intelligent creature as its representative. Then the representatives of two adjacent islands in the circular arrangement become friends, forming extra edges between islands.

Lostmonkey, the guardian of Neverland, wishes to estimate the maximum total combat power available in the worst-case scenario. Due to the synergy among friends, fighting together increases combat power. However, in this scenario, Lostmonkey wants to select a set of creatures with no two friends such that the sum of their combat power is maximized.

Formally, suppose there are n islands. For each island, the input is given as follows:

• If the island has only one creature, then let its combat power be w. In this case, if the creature is selected its value is w, otherwise 0.
• If an island has m = 2k+1 creatures (a windmill graph), then the first creature is the representative (center) with combat power w₀ and each subsequent pair of creatures (wing vertices) have combat powers w₁ and w₂. In such an island, if the representative is chosen then no other creature in that island can be chosen and the island contributes w₀. Otherwise, one may choose from each pair at most one creature (since they are connected by an edge), contributing sum(max(w₁, w₂)) over the k pairs.

In addition, representatives of adjacent islands (in a cycle) are connected by an edge. In the final selection, no two creatures (whether from the same island or from different islands) that are friends may both be selected.

You are given the combat power for every creature in each island. Your task is to choose a set of creatures such that no two selected creatures are friends (either within an island or between representatives of neighboring islands) and the total combat power is maximized.

Input Format: The first line contains an integer n representing the number of islands. Then for each island, there is a line containing an integer m (number of creatures) followed by m space-separated integers indicating the combat power of each creature. For islands with m = 1, the only creature is both the representative and the sole inhabitant. For islands with m > 1, m is always an odd number (i.e. m = 2k+1) and the first creature is the representative.

Output Format: Output a single integer denoting the maximum total combat power achievable under the constraint that no two friends are selected.

Mathematical Formulation:

For each island i, define two values:

• R1[i] = combat power of the representative.
• R0[i] = sum over each pair \( (w_{2j-1}, w_{2j}) \) for \(j = 1,2,\dots,k\) of \(\max(w_{2j-1}, w_{2j})\).

Then the overall answer is computed by handling the cycle constraint among islands. That is, if we let a binary choice for each island where choosing 1 means selecting the representative and 0 means not selecting the representative (thus collecting \(R0[i]\)), then the representatives of two adjacent islands cannot both be chosen. You need to maximize \(\sum_{i=1}^{n} \big( x_i \cdot R1[i] + (1-x_i) \cdot R0[i]\big)\) subject to \(x_i \in \{0,1\}\) and for all adjacent islands (in the cycle), \(x_i + x_{i+1} \leq 1\) (with island n adjacent to island 1).

inputFormat

The input begins with an integer n (number of islands). The following n lines each describe an island. Each line starts with an integer m (the number of creatures on the island), followed by m space‐separated positive integers (the combat power for each creature). For islands with m = 1, the single creature is the representative. For islands with m > 1, m is odd (i.e. m = 2k+1) with the first creature being the representative and the remaining creatures forming k pairs.

outputFormat

Output a single integer representing the maximum total combat power that can be achieved by selecting a subset of creatures such that no two friends (either within an island or among adjacent islands’ representatives) are both selected.

sample

1
1 10

10

</p>