Background

The otaku JYY loves playing RPG games and always wants to spend the minimum amount of time to watch all the side quests. Recently, JYY bought a new genuine RPG game, so JYY can finally "save" and "load" the game!

Problem Statement

In the RPG game JYY is currently playing, there are $N$ plot points, numbered from $1$ to $N$. From the $i$-th plot point, depending on JYY's choices, one can follow different side quests to reach $K_i$ different new plot points. Of course, if $K_i = 0$, it means that plot point $i$ is one of the game's endings.

Watching a side quest takes a certain amount of time.

JYY starts at plot point $1$, which is the beginning of the game.

The game JYY bought is special: the side path from the start of the game to any plot point is unique.

Furthermore, every plot point is reachable from plot point $1$.

Similar to his previous RPG game, JYY can choose to restart the game at any time, i.e., return to plot point $1$. However, there is a difference: since JYY bought the genuine software, every time JYY reaches a plot point, he can "save" and "load". Unfortunately, JYY's RPG game only has one save slot: every "save" operation overwrites the previous save.

For example, if JYY performs a "save" operation at plot point $x$, then whenever JYY reaches any plot point (including endings) afterwards, he can "load" and immediately return to plot point $x$. But if JYY later performs a "save" at plot point $y$, then any subsequent "load" will only return him to plot point $y$.

Initially, the save slot contains no information, so JYY can only perform a "load" operation after performing at least one "save" operation.

"Load", "save", and "restart" operations take zero time.

Watching the same side quest repeatedly is painful. JYY wants to spend the minimum amount of time to watch all different side quests.

Input

The first line contains a positive integer $N$.

The next $N$ lines each contain information about the $i$-th plot point.

The first non-negative integer in each line is $K_i$. This is followed by $K_i$ pairs of integers, $b_{i,j}$ and $t_{i,j}$, representing that from plot point $i$, one can travel to plot point $b_{i,j}$, and watching this side quest takes $t_{i,j}$ time.

Output

Output a single integer representing the minimum time required for JYY to watch all side quests.

Examples

Input 1

9
2 5 1 2 1
2 3 1 6 1
2 7 1 4 1
2 8 1 9 1
0
0
0
0
0

Output 1

8

Note 1

Let "load" denote loading, "save" denote saving, and "restart" denote restarting. The optimal route is:

1→5→restart→2→save→6→load→3→save→7→load→4→save→8→load→9

Constraints

For $10\%$ of the data, $N = 7$.

For $40\%$ of the data, $N \leq 90$.

For $70\%$ of the data, $N \leq 10^5$, $K_i \leq 2$.

For $100\%$ of the data, $N \leq 10^6$, $1 \leq t_{i,j} \leq 10^4$, $\sum_{i=1}^{N} K_i = N-1$.