Andy is addicted to Minecraft. One day, he decides to download a new mod to enhance his gaming experience. The mod adds a million types of ores into the game, numbered from to
, and requires a subset
of distinct ores to be chosen. The mod then provides two new crafting recipes:
- Combine one ore of each type in
, and summon a Herobrine with power
, where
denotes the size of subset
.
- Combine two Herobrines with powers
and
into a single Herobrine with power
.
Note that ingredients are destroyed once they are combined in a recipe.
Andy has to mine for these ores. The mine currently consists of chambers labelled from
to
, and
tunnels labelled from
to
. The
-th chamber consists of
ores which Andy can mine,
. The
-th tunnel connects chambers
and
(
), with the outside being considered as chamber
.
Andy decides to begin mining in chamber . Overhearing his plans, Josh decides to block the
-th tunnel with bedrock. Andy's only chance to escape is to summon a Herobrine to break the bedrock. Therefore, Andy decides to collect all the ores from chambers reachable from chamber
via unblocked tunnels, and to create a single Herobrine with the maximum possible power.
Mike would like to know the power of Andy's Herobrine, but as he is currently looting a village, he has no idea which chamber Andy is in. Therefore, he wants to know: for each value of between
and
, across all possible subsets
, what is the maximum possible power of Andy's Herobrine? Note that
may differ for different values of
.
Constraints
for all
Subtask 1 [20%]
Subtask 2 [40%]
for all
.
Subtask 3 [40%]
No additional constraints.
Input Specification
The first line contains one integer, .
The second line contains integers,
.
The -th of the following
lines contains one integer,
, followed by
integers,
.
Output Specification
Output lines. The
-th line should contain one integer, denoting the maximum possible power of Andy's Herobrine if
.
Sample Input
6
0 1 2 2 3 3
4 1 1 2 2
3 1 2 3
2 2 3
2 1 3
4 1 2 3 4
3 1 3 4
Sample Output
15
9
8
2
4
3
Explanation
Suppose , so that the second tunnel which connects chambers
and
is blocked with bedrock. Then, Andy can reach all chambers except chamber
.
In total, Andy can mine ores of type
,
ores of type
,
ores of type
, and
ores of type
.
If he chooses , then he can create
Herobrines of power
using the first crafting recipe. Using the second crafting recipe, he can combine two Herobrines to form a Herobrine with power
. Using the second crafting recipe again, he can combine the two remaining Herobrines to form a single Herobrine with power
. It can be shown that this choice of
and this sequence of crafting operations is optimal.
Comments