Організаторські проблеми: тема для дисертації?#1978

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

2 секунди
64 мегабайти
Легка

Організатори Зимової школи в Харкові зіткнулися з найбільшими труднощами не під час самого заходу, а на етапі підготовки. День у день пісня «Ще не вечір...» звучала все тихіше, і виконував її не Лайма Вайкуле, а Олександр Вечур. Чим ближче було відкриття школи, тим швидше вечоріло, але ясності щодо проблем, що виникали, не додавалося.

Проблема полягала в тому, що всі лекторів, які мали читати лекції та організовувати контести, незалежно один від одного обирали теми лекцій та задачі без жодної координації. Коли організатори зібрали всі ці пропозиції, вони розгубилися: як зробити Зимову школу максимально ефективною та корисною в умовах цього науково-теоретичного хаосу? Олександр Вечур вирішив, що тут потрібен масштабний експеримент у Харківському національному університеті радіоелектроніки, а також теоретичні дослідження. До експерименту охоче підключилася група волонтерів, що стихійно сформувалася зі студентів. Метою було оцінити корисність кожної теми, яку збиралися презентувати лектори. Завдяки підготовці до дисертації Олександр швидко здогадався, що корисність кожної теми залежить від порядку, у якому лектори їх доповідатимуть. Волонтерам треба було з'ясувати, що експеримент слід повторити декілька разів, щоб визначити цю залежність. Студенти навіть не сперечалися — чого лише не зробиш, щоб не ходити на пари?.. :)

Щоб слухачі (і студенти) змогли засвоїти певні теми, необхідно, щоб перед цим були розкриті деякі інші теми: деякі доведення спираються на факти з інших тем. Проте, якщо у залежностях тем утворюється цикл, усі теми все одно можна включити, оскільки це не вплине на розуміння матеріалу експериментальними слухачами та майбутніми студентами.

Тепер у Олександра Вечура є результати експерименту, і необхідно скласти список тем лекцій так, щоб слухачі Зимової школи зрозуміли все, а сумарна корисність школи була максимальною.

Вхідні дані

У першому рядку вхідного файлу записано одне число (1 \leq N \leq 200).

У другому рядку записано цілих чисел, кожне з яких не перевищує за модулем, — корисності відповідних тем.

Далі йдуть рядків, у кожному з яких описуються залежності відповідної теми. Опис починається з кількості тем, які потрібно засвоїти, щоб зрозуміти цю тему, а потім перелічені номери цих тем через пробіл.

Вихідні дані

Виведіть одне число — максимально можливу сумарну корисність Зимової школи.

Приклади

Приклад 1

Loading
Loading