Maximizing Lecture Attendance

You are given \(n\) lectures and \(m\) students. Each lecture \(i\) has a capacity \(c_i\). Each student has a list of lectures they are willing to attend. Each student can attend at most one lecture, and a lecture cannot host more students than its capacity.

The goal is to assign students to lectures such that the total number of students attending a lecture is maximized. Formally, if we let \(S\) be the set of students and for each student \(s \in S\) let \(P(s)\) be the set of lectures they prefer, then you need to choose at most one lecture for each student such that, for every lecture \(i\), the number of students assigned to \(i\) does not exceed \(c_i\). Output the maximum number of students that can be assigned.

inputFormat

The input is read from standard input in the following format:

• The first line contains two integers \(n\) and \(m\), representing the number of lectures and the number of students respectively.
• The second line contains \(n\) integers \(c_0, c_1, \dots, c_{n-1}\) where \(c_i\) is the capacity of lecture \(i\).
• The next \(m\) lines each describe a student's preferences. Each line starts with an integer \(k\) (the number of lectures the student can attend) followed by \(k\) integers indicating the lecture indices.

All tokens are separated by whitespace.

outputFormat

Output a single integer to standard output representing the maximum number of students that can attend a lecture under the given constraints.

3 3
1 2 1
2 0 1
2 1 2
2 0 2

3