Details#4851

Details

1 second

128 megabytes

Easy

The company Auto-2012 produces engines for world-famous cars. The engine consists of exactly $n$ details, numbered from $1$ to $n$ , while the detail with the number $i$ is manufactured for $p_{i}$ p_i seconds. Specificity of the enterprise Auto-2012 is that only one engine component can be manufactured at a time. To produce some details, you must have a pre-made set of other details.

The general director of Auto-2012 set before the company an ambitious task - for the shortest time to make the detail number $1$ to present it at the exhibition.

Write a program that, according to the given dependences of the order of production between the details, finds the shortest time for which you can make a detail with number $1$ .

Input

The first line contains $n$ ( $1 \leq n \leq 1 0^{5}$ 1 \le n \le 10^5) integers $p_{1}, p_{2}, \dots, p_{n}$ p_1, p_2, \ldots, p_n giving the manufacturing time of each detail in seconds.

Each of the following $n$ lines describes the characteristics of the details production. Here $i$ -th line contains the list of details that are required for the production of the detail with the number $i$ . There are no duplicate detail numbers in the list. The list can also be empty - then it will have an empty string! The sum of the lengths of all lists does not exceed $200000$ .

It is known that there are no cyclical dependencies in the production of details.

Output

Print the minimum time (in seconds) required for the speedy production of the detail with number $1$ .

Examples

Input	Output
4 8 8 7<br>2 3<br>4<br><br>	19

Example 1

Example 2

Note

For the example, the optimal path:

Manufacture details $4$ , $2$ and $3$ one after another.
Then manufacture detail $1$ .

Total time $7 + 8 + 8 + 4 = 27$ 7 + 8 + 8 + 4 = 27, but since details $2$ and $3$ can be manufactured in parallel after manufacturing detail $4$ , we need to consider the longest chain — $7 + 8 + 4 = 19$ 7 + 8 + 4 = 19.