Organizational Problems: A Topic for a Dissertation?
The organizers of the "Winter School in Kharkiv" encountered their greatest challenges not during the event itself, but in the preparation phase. Each day, the song "It's Not Evening Yet..." became fainter, not sung by Laima Vaikule, but by Oleksandr Vechur. As the school's opening drew near, the evenings darkened, yet clarity on the emerging issues remained elusive.
The problem was that all N lecturers, responsible for delivering lectures and organizing contests, independently selected their lecture topics and tasks without any coordination. When the organizers compiled all these proposals, they were perplexed: how could they make the Winter School as effective and beneficial as possible amidst this scientific and theoretical chaos? Oleksandr Vechur concluded that a large-scale experiment at the Kharkiv National University of Radio Electronics, along with theoretical research, was essential. A group of volunteers, spontaneously emerging from the student body, eagerly joined the experiment. The objective was to assess the usefulness of each topic to be presented by the lecturers. Thanks to his dissertation preparation, Oleksandr quickly realized that the usefulness of each topic depended on the order in which the lecturers presented them. The volunteers needed to understand the necessity of conducting the experiment multiple times to determine this dependency. The students didn't even argue—what wouldn't they do to skip classes?.. :)
For the listeners (and students) to grasp certain topics, it is necessary for some other topics to be covered first, as some proofs rely on facts from other topics. However, if there is a cycle of topic dependencies, all topics can still be covered, as it will not impact the students' understanding of the material during the experiment, nor the future listeners.
Now, Oleksandr Vechur has the experimental results and needs to compile a list of lecture topics to ensure that the Winter School attendees understand everything and that the total usefulness of the Winter School is maximized.
Input
The first line of the input file contains a single number - N (1 ≤ N ≤ 200). The second line contains N integers, each not exceeding 1000 in absolute value - representing the usefulness of each topic. Following this are N lines describing the dependencies of the topics. Each description begins with the number of topics that need to be understood to comprehend the given topic, followed by the numbers of these topics, separated by spaces.
Output
Output a single number - the maximum possible total usefulness of the Winter School.