수강 부담

한 대학교에는 들을 만한 훌륭한 강의가 아주 많습니다. 알고리즘, 무대 분장, 우주, 요가, 리더십 등 다양한 강의가 열립니다. 하지만 어떤 강의를 들을지 정하려고 하면 항상 두 가지 문제에 부딪힙니다.

• 가장 흥미로운 강의들은 서로 수업 시간이 겹치기 마련입니다.
• 하루에 공부하고 과제할 수 있는 시간은 한정되어 있습니다.

이를 체계적으로 다루기 위해 최적화 문제로 모델링합니다. 각 강의 $i$ 에는 그 강의를 들었을 때 얻는 이득(재미, 실무 능력 등 무엇이든)을 나타내는 효용 $u_i$ 가 있습니다. 또한 각 강의에는 그 강의를 통과하기 위해 매주 필요한 학습량을 나타내는 부담 $w_i$ 가 있습니다. (부담은 그 강의가 매주 몇 번 열리는지와 반드시 비례하지는 않습니다.) 마지막으로, 각 강의는 한 주 동안 정해진 여러 개의 수업 시간대를 차지합니다.

선택한 강의들끼리 수업 시간대가 서로 겹치지 않고, 부담의 합이 여러분의 학습 용량 $C$ 를 넘지 않도록 강의 집합을 골라 전체 효용의 합을 최대화하세요.

첫째 줄에 데이터 세트의 개수 $K \ge 1$ 이 주어집니다. 이어서 $K$ 개의 데이터 세트가 다음 형식으로 주어집니다.

각 데이터 세트의 첫 줄에는 세 정수 $n$, $m$, $C$ 가 주어집니다.

• $1 \le n \le 20$ : 고려 중인 강의의 수
• $1 \le m \le 100$ : 한 주의 수업 시간대의 수 (예: "월요일 3:30-4:50" 이 하나의 시간대)
• $1 \le C \le 100$ : 학습 용량

그다음 $n$ 개의 줄에는 각각 하나의 강의가 설명됩니다. 강의 $i$ 의 줄에는 정수 효용 $u_i \ge 0$, 부담 $w_i \ge 0$, 수업 횟수 $m_i$ 가 차례로 주어지고, 이어서 그 강의가 차지하는 시간대를 나타내는 $1$ 이상 $m$ 이하의 정수 $m_i$ 개가 주어집니다.

각 데이터 세트마다 먼저 "Data Set x:" 를 한 줄에 출력합니다. 여기서 $x$ 는 데이터 세트의 번호이며 $1$ 부터 시작합니다. 그다음 줄에, 수업 시간대가 서로 겹치지 않으면서 부담의 합이 $C$ 이하인 강의 집합으로 얻을 수 있는 최대 총 효용을 출력합니다. (어떤 강의들이 이 효용을 달성하는지는 출력할 필요가 없습니다.)