E. Закупка множеств
ограничение по времени на тест
2 seconds
ограничение по памяти на тест
256 megabytes
ввод
стандартный ввод
вывод
стандартный вывод
СЪЕЛ ОУЖАС.
Рабочее название задачи

Вирус Хексадесимал очень любит играть с числовыми множествами — пересекать их, объединять. В один прекрасный день она с удивлением обнаружила, что Сказзи, ее ручной сферический кот, объединил все множества в одно и съел результат! Надо было срочно что-то делать, и Хексадесимал полетела на рынок.

На рынке продается n числовых множеств. Вирус хочет купить такой набор множеств, что количество множеств в нем будет равно количеству чисел в его объединении. Из всех подходящих наборов множеств она готова выбрать только самый дешевый.

Но не все так просто! Поскольку в Мэйнфрейме царит рынок совершенной конкуренции, то известно, что объединение любых k множеств содержит не менее k различных чисел (для любого целого положительного k).

Помогите вирусу выбрать подходящий набор множеств. Этот набор может быть пустым.

Входные данные

В первой строке дано единственное целое число n (1 ≤ n ≤ 300) — количество числовых множеств на рынке.

Последующие n строк описывают товар: сперва дано mi (1 ≤ mi ≤ n) — количество различных чисел в i-ом множестве, затем mi чисел — элементы множества. Известно, что элементы множества — целые положительные числа, не превосходящие n.

В последней строке содержится n целых чисел, по модулю не превосходящих 106 — стоимости каждого из множеств.

Выходные данные

Выведите одно число — минимальную стоимость покупки такого набора из k множеств, что объединение множеств этого набора содержит ровно k чисел ().

Примеры
Входные данные
3
1 1
2 2 3
1 3
10 20 -3
Выходные данные
-3
Входные данные
5
2 1 2
2 2 3
2 3 4
2 4 5
2 5 1
1 -1 1 -1 1
Выходные данные
0
Входные данные
5
2 1 2
2 2 3
2 3 4
2 4 5
2 5 1
-1 1 -1 1 -1
Выходные данные
-1