Monster Annihilation

In this game, the hero JYY can attack monsters in two ways: a normal attack and a magical attack. Both attacks consume a certain amount of energy. While a normal attack does not completely kill a monster, it causes the monster's corpse to transform into some new monsters. In particular, after one or more normal attacks, a monster may reappear as one or more monsters of the same type. In contrast, a magical attack will completely kill a monster. Generally speaking, a magical attack costs more energy than a normal attack (although a bug in the game system does not guarantee this).

There are \(N\) different types of monsters in the game world, numbered from 1 to \(N\). At the moment, monster type 1 is invading the village. JYY wants to know the minimum amount of energy required to completely eliminate all monsters in the village.

The process for handling a monster of type \(i\) is as follows:

1. You may use a magical attack which costs \(B_i\) energy and immediately kills the monster.
2. Alternatively, you may use a normal attack which costs \(A_i\) energy, but the monster will not be fully defeated. Instead, it transforms into a list of monsters. Suppose that when a monster of type \(i\) is hit with a normal attack, it produces monsters of types \(t_{i,1}, t_{i,2}, \dots, t_{i,k_i}\). You must then eliminate all of the resulting monsters.

Your task is to determine the minimum energy required to completely eliminate the initial invading monster (of type 1).

This can be formulated as computing a function \(f(i)\) for each monster type \(i\) defined by:

[ f(i) = \min\Bigl(B_i,; A_i + \sum_{j=1}^{k_i} f(t_{i,j})\Bigr), \quad 1 \le i \le N. ]

Note that cycles may exist (for example, a monster may produce another monster of the same type). It is guaranteed that all energy costs are non-negative and that the minimal solution is well defined.

inputFormat

The input begins with a single integer \(N\) (\(1 \le N \le 1000\)), the number of monster types. Then \(N\) blocks follow. For each monster type \(i\) (\(1 \le i \le N\)), there are two lines:

1. The first line contains two integers \(A_i\) and \(B_i\) (\(0 \le A_i, B_i \le 10^9\)), representing the energy cost of a normal attack and a magical attack on a monster of type \(i\), respectively.
2. The second line starts with an integer \(k_i\) (the number of monsters produced if a normal attack is used), followed by \(k_i\) integers \(t_{i,1}, t_{i,2}, \dots, t_{i,k_i}\) (each between 1 and \(N\)), representing the types of monsters that appear after a normal attack on monster \(i\). Note that \(k_i\) can be zero; in that case a normal attack effectively does not produce additional monsters.

The initial invading monster is always of type 1.

outputFormat

Output a single integer, the minimum amount of energy required to completely eliminate all monsters in the village.

sample

1
3 5
1 1

5