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 pi 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 ≤ n ≤ 105) integers p1, p2, ..., pn 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.