Side Stories

Background

JYY is a huge fan of RPG games like Chinese Paladin and Xuan-Yuan Sword. However, what JYY enjoys most is not the combat, but the drama-like storylines filled with love, hate, and grudges. These games often feature many side stories, and JYY wants to spend the minimum amount of time to watch all of them.

Description

In the RPG game JYY is currently playing, there are $N$ plot points, numbered from $1$ to $N$. From the $i$-th plot point, JYY can choose to follow different side stories to reach $K_i$ different new plot points. If $K_i = 0$, it means the $i$-th plot point is an ending of the game.

Watching a side story takes a certain amount of time.

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

Clearly, every plot point is reachable from plot point $1$. Furthermore, as the game progresses, the plot is irreversible. Therefore, the game guarantees that from any plot point, it is impossible to return to that same plot point.

Because JYY overused a cheat tool, the game's "save" and "load" functions are broken. The only way for JYY to return to a previous plot point is to quit the current game and start a new one, which means returning to plot point $1$. JYY can quit the game and restart at any time.

Constantly starting new games and re-watching already seen plot points is very tedious. JYY wants to spend the minimum amount of time to watch all the different side stories.

Input

The first line contains a positive integer $N$.

The next $N$ lines each contain information about the $i$-th plot point: The first integer is $K_i$, followed by $K_i$ pairs of integers, $b_{ij}$ and $t_{ij}$, representing that from plot point $i$, one can travel to plot point $b_{ij}$, and watching this side story takes $t_{ij}$ time.

Output

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

Examples

Input 1

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

Output 1

24

Note

JYY needs to restart the game 3 times. Including the initial game, the 4 game sessions are: $1 \to 2 \to 4$, $1 \to 2 \to 5$, $1 \to 3 \to 5$, and $1 \to 3 \to 6$.

Constraints

For 30% of the data: $N \le 25, \sum_{i=1}^N K_i \le 100$; For 70% of the data: $N \le 100, \sum_{i=1}^N K_i \le 2000$; For 100% of the data: $N \le 300, 0 \le K_i \le 50, 1 \le t_{ij} \le 300, \sum_{i=1}^N K_i \le 5000$.