Description

In the RPG that JYY is currently playing, there are $N$ storyline points, numbered $1$ to $N$. At the $i$-th storyline point, depending on JYY’s choices, he can go through different branching storylines to $K_i$ different new storyline points. If $K_i = 0$, then point $i$ is an ending of the game.

Watching a single branching storyline takes some time. JYY starts at storyline point $1$, which is the beginning of the game. Clearly, every storyline point is reachable from point $1$. Moreover, as the game progresses, the storyline is irreversible. Therefore, the game guarantees that starting from any storyline point, you can never return to this point again.

Due to JYY’s excessive use of modifiers, the game’s “save” and “load” features are broken. The only way to return to a previous storyline point is to quit the current game and start a new game, i.e., return to point $1$. JYY may quit and restart at any time. Repeatedly starting new games to rewatch already seen storylines is painful, so JYY wants to minimize the total time to watch all different branching storylines.

Input Format

The first line contains a single positive integer $N$.

Then follow $N$ lines. The $i$-th line describes storyline point $i$:

• The first integer is $K_i$, followed by $K_i$ pairs of integers $b_{i,j}$ and $t_{i,j}$, indicating that from storyline point $i$ you can go to storyline point $b_{i,j}$, and watching this branching storyline takes $t_{i,j}$ time.

Output Format

Output a single integer on one line, the minimum total time JYY needs to watch all branching storylines.

6
2 2 1 3 2
2 4 3 5 4
2 5 5 6 6
0
0
0

24

Hint

Sample explanation:

JYY needs to restart the game $3$ times. Together with the initial playthrough, the $4$ playthroughs are:

• $1 \to 2 \to 4$.
• $1 \to 2 \to 5$.
• $1 \to 3 \to 5$.
• $1 \to 3 \to 6$.

Constraints:

For $100\%$ of the testdata, $N \le 300$, $0 \le K_i \le 50$, $1 \le t_{i,j} \le 300$, $\sum K_i \le 5000$.

Translated by ChatGPT 5