Course Load

A university offers a large number of fantastic courses you might want to take: classes on algorithms, stage make-up, the universe, yoga, leadership, and many more. Whenever you try to decide which classes to take, you always run into two problems:

• The most exciting classes always overlap with one another.
• There are only so many hours in the day to work and study.

To be systematic about it, model this as an optimization problem. For each class $i$ you assign a utility $u_i$: the benefit you would derive from taking it (fun, job skills, or whatever else). Each class also has a workload $w_i$: the units of work per week required to pass. (The workload need not correlate with how often the class meets per week.) Finally, each class occupies a fixed set of meeting slots during the week.

Select a set of classes that do not overlap in their meeting times and whose total workload does not exceed your work capacity $C$, so as to maximize your total utility.

The first line contains a number $K \ge 1$, the number of data sets in the input. It is followed by $K$ data sets, each of the following form.

The first line of a data set contains three integers $n$, $m$, and $C$:

• $1 \le n \le 20$ is the number of classes you are considering.
• $1 \le m \le 100$ is the number of class meeting slots in the week (a meeting slot could be, for instance, "Monday 3:30-4:50").
• $1 \le C \le 100$ is your capacity for class work.

This is followed by $n$ lines, each describing one class. For class $i$, the line contains the integer utility $u_i \ge 0$, then the workload $w_i \ge 0$, then the number of meetings $m_i$, followed by $m_i$ integers between $1$ and $m$ giving the meeting slots the class occupies.

For each data set, first output a line "Data Set x:" by itself, where $x$ is the data set's number (starting from $1$). Then, on the next line, output the maximum total utility achievable by any set of non-overlapping classes whose total workload is at most $C$. (You do not need to output which classes achieve this utility.)