Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems.
×

Package for this problem was not updated by the problem writer or Codeforces administration after we’ve upgraded the judging servers. To adjust the time limit constraint, solution execution time will be multiplied by 2. For example, if your solution works for 400 ms on judging servers, then value 800 ms will be displayed and used to determine the verdict.

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

E. Buying Sets

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputThe Hexadecimal virus loves playing with number sets — intersecting them, uniting them. One beautiful day she was surprised to find out that Scuzzy, her spherical pet cat, united all sets in one and ate the result! Something had to be done quickly and Hexadecimal rushed to the market.

The market has *n* sets of numbers on sale. The virus wants to buy the following collection of sets: the number of sets in the collection should be exactly the same as the number of numbers in the union of all bought sets. Moreover, Hexadecimal wants to buy the cheapest suitable collection of set.

Yet nothing's so easy! As Mainframe is a kingdom of pure rivalry markets, we know that the union of any *k* sets contains no less than *k* distinct numbers (for every positive integer *k*).

Help the virus choose the suitable collection of sets. The collection can be empty.

Input

The first line contains the only number *n* (1 ≤ *n* ≤ 300) — the number of sets available in the market.

Next *n* lines describe the goods: first we are given *m* _{ i} (1 ≤ *m* _{ i} ≤ *n*) — the number of distinct numbers in the *i*-th set, then follow *m* _{ i} numbers — the set's elements. We know that the set's elements are distinct positive integers and they do not exceed *n*.

The last line contains *n* integers whose absolute values do not exceed 10^{6} — the price of each set.

Output

Print a single number — the minimum price the virus will have to pay for such a collection of *k* sets that union of the collection's sets would have exactly *k* distinct numbers ().

Examples

Input

3

1 1

2 2 3

1 3

10 20 -3

Output

-3

Input

5

2 1 2

2 2 3

2 3 4

2 4 5

2 5 1

1 -1 1 -1 1

Output

0

Input

5

2 1 2

2 2 3

2 3 4

2 4 5

2 5 1

-1 1 -1 1 -1

Output

-1

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jul/07/2020 22:36:48 (i2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|