| Codeforces Beta Round 80 (Div. 1 Only) |
|---|
| Закончено |
Вирус Хексадесимал очень любит играть с числовыми множествами — пересекать их, объединять. В один прекрасный день она с удивлением обнаружила, что Сказзи, ее ручной сферический кот, объединил все множества в одно и съел результат! Надо было срочно что-то делать, и Хексадесимал полетела на рынок.
На рынке продается 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
