Description

With Labor Day approaching, an underground supermarket plans to temporarily call in security guards from other units to direct and ease the flow of dense crowds and vehicles, so as to avoid chaos and congestion inside the supermarket.

All passages in the underground supermarket form a tree. Some passages can be seen from one another. The general manager requires every endpoint of every passage (i.e., every tree vertex) to be watched around the clock. The cost of assigning a guard at different passage endpoints varies.

If a guard stands at one endpoint of a passage, then besides guarding the endpoint where they stand, they can also see the other endpoint of that passage. Therefore, a single guard may be able to watch multiple endpoints (tree vertices), and it is not necessary to assign a guard to every endpoint of every passage.

Task:

Please help the supermarket manager plan the arrangement so that all passage endpoints are watched, while minimizing the total cost.

Input Format

The first line contains $n$, the number of nodes in the tree.

Lines $2$ through $n+1$ each describe one passage endpoint (node), in the following order: the node label $i$ ($0 < i \le n$), the cost $k$ of placing a guard at this node ($1 \le k \le 10000$), the number of children of this node $m$, followed by $m$ integers, which are the labels of this node’s $m$ children $r_1, r_2, \cdots, r_m$.

For a tree with $n$ ($0 < n \le 1500$) nodes, node labels are between $1$ and $n$, and labels are not repeated.

Output Format

Output a single integer on one line: the minimum total cost.

6
1 30 3 2 3 4
2 16 2 5 6
3 5 0
4 4 0
5 11 0
6 5 0

25

Hint

Sample explanation:

Placing $3$ guards at nodes $2, 3, 4$ can watch all $6$ nodes, and the minimum cost is $25$.

Translated by ChatGPT 5