P4043 [AHOI2014/JSOI2014] Branching Storylines

Homebody JYY really enjoys playing RPGs, such as Xianjian and Xuanyuanjian. However, JYY is not fond of combat scenes, but rather the drama-like storylines full of love and hate. These games often have many branching storylines. Now JYY wants to spend the least amount of time to watch all branching storylines.

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.

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 a single integer on one line, the minimum total time JYY needs to watch all branching storylines.

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