Background

In his long-term life as a shut-in, JYY has discovered a new RPG game. In this game, JYY plays as a heroic knight who uses his longsword to slay monsters invading the village.

Description

In this game, JYY has two ways to attack: a normal attack and a magic attack. Both types of attacks consume some of JYY's stamina.

Using a normal attack on a monster does not kill it completely; the monster's corpse can transform into other new monsters. Note that a monster might transform back into one or more of the same type of monster after several normal attacks. Using a magic attack, however, can completely kill a monster. Generally, magic attacks consume more stamina than normal attacks (though due to a bug in the game system, this is not guaranteed).

There are $N$ different types of monsters in the game world, numbered from 1 to $N$. Now, monster type 1 has invaded the village. JYY wants to know the minimum stamina required to completely kill all the monsters in the village.

Input

The first line contains an integer $N$.

The next $N$ lines each describe a monster. The $i$-th line contains several integers. The first three integers are $S_i$, $K_i$, and $R_i$, representing that for monster $i$, a normal attack consumes $S_i$ stamina, a magic attack consumes $K_i$ stamina, and after the monster $i$ dies from a normal attack, it produces $R_i$ new monsters. The following $R_i$ integers are between 1 and $N$ and are not equal to $i$, representing the IDs of the newly appearing monsters. Multiple monsters of the same ID can appear.

Output

Output a single integer representing the minimum stamina required.

Constraints

• For 20% of the data: $N \le 5$.
• For 50% of the data: $N \le 300$.
• For 100% of the data: $2 \le N \le 2 \times 10^5$, $1 \le R_i$, $\sum_{i=1}^N R_i \le 10^6$, $1 \le K_i, S_i \le 5 \times 10^{14}$.

Examples

Input 1

4
4 27 3 2 3 2
3 5 1 2
1 13 2 4 2
5 6 1 2

Output 1

26

Note

First, use a normal attack consuming 4 stamina; the resulting monsters are 2, 2, and 3. Spend 10 stamina to use magic attacks to kill the two monsters of type 2. For the remaining monster of type 3, spend 1 stamina for a normal attack. At this point, the monsters in the village are of type 2 and 4. Finally, spend 11 stamina to use magic attacks to completely kill these two monsters.

The total stamina spent is $4+5+5+1+5+6=26$.