eolymp
bolt
Try our new interface for solving problems
Problems

Организаторские проблемы: тема для диссертации?

Организаторские проблемы: тема для диссертации?

Time limit 2 seconds
Memory limit 64 MiB

У организаторов "Зимней Школы в Харькове" наибольшие проблемы, как это ни странно, возникали не во время проведения самой школы, а во время подготовки к её проведению. И каждый день всё тише и тише звучала песня "Ещё не вечер…", но в исполнении не Лаймы Вайкуле, а Александра Вечура – с каждым днём приближения открытия школы вечера становились темнее, но просветления в вырисовывавшейся проблеме не наступало.

А проблема состояла в том, что все N лекторов, которые будут читать лекции и проводить контесты, тематику как лекций, так и тем более задач, подбирают самостоятельно, не согласовывая друг с другом. Организаторы же, собрав все их предложения в единое целое, схватились за голову: как сделать Зимнюю Школу при этом научно загромождённом теоретическом беспорядке наиболее эффективной и полезной? Тут без масштабного эксперимента на базе ХНУРЭ и теоретических исследований не обойтись, решил Александр Вечур, и группа неизвестно откуда возникших волонтёров из числа студентов мгновенно включилась в эксперимент, целью которого было определить полезность каждой темы, которая будет читаться лекторами. Подготовка диссертации даром не прошла – Александр быстро понял, что полезность каждой из тем зависит от того, в каком порядке лекторы будут эти лекции читать. Пришлось волонтёрам объяснять необходимость неоднократного повторения эксперимента, для определения этой зависимости. Студенты даже не спорили – чего не сделаешь ради того, чтобы на пары не ходить?.. :)

Для того что бы слушатели (и студенты) поняли некоторые темы, необходимо, чтобы были прочитаны так же некоторые другие темы, так как некоторые доказательства базируются на фактах из других тем. Однако если существует цикл из зависимостей тем, то их все можно прочитать, так как на качестве понимания материала студентами, участвующими в эксперименте, и, естественно, будущими слушателями это не скажется.

Теперь у Александра Вечура на руках результаты экспериментов и ему нужно составить список тем лекций, которые должны быть прочитаны таким образом, чтобы слушатели Зимней Школы всё поняли и суммарная полезность самой Зимней Школы была максимальной.

Input data

Первая строка входного файла содержит одно число - N (1N200). Вторая строка содержит N целых чисел, не превосходящих по модулю 1000 - полезности каждой темы. Далее следуют N строк с описанием зависимостей тем. Каждое описание начинается количеством тем, которые необходимо понять для понимания данной темы. Потом следуют номера этих тем, разделенные пробелами.

Output data

Выведите единственное число - максимально возможную суммарную полезность Зимней Школы.

Examples

Input example #1
4
-1 1 -2 2
0
1 1
2 4 2
1 1
Output example #1
2