Course Load

Time limit1sMemory limit128 MB

Summary

Pick a set of classes with pairwise disjoint meeting slots and total workload at most C, maximizing total utility.

Level: Medium6 of 10
Topics: Dynamic programming, Bit manipulation, Brute force
Solved: No attempts yet

Problem

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.

Input

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.

Output

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.)

Examples3

Example 1

Input

2
3 5 5
5 4 2 1 4
3 2 3 2 3 5
1 1 1 4
3 5 5
1 1 3 1 3 5
1 1 2 1 2
1 1 2 4 5

Expected output

Data Set 1:
5
Data Set 2:
2

Example 2

Input

Expected output

Data Set 1:
11

Example 3
Input
```
1
2 3 10
5 1 1 1
9 1 1 1
```
Expected output
```
Data Set 1:
9
```