# Topological sort

# Details

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`

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._{i}

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** ≤ **n** ≤ `10`

) integers ^{5}`p`

, _{1}`p`

, ..., _{2}`p`

giving the manufacturing time of each detail in seconds._{n}

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**.

100 200 300 2 2 1

300

3 5 1 2 3 1 4 4

6