철도망 확장

어느 도시가 대중교통 철도망을 확장하려고 합니다. 여러 개의 확장 노선이 후보로 논의되고 있지만 예산이 한정되어 있어 일부만 건설할 수 있습니다. 예산을 넘지 않는 범위에서 후보 노선의 부분집합을 골라, 모든 승객의 총 이동 시간을 최대한 줄이는 것이 목표입니다.

현재 철도망과 최대 10개의 확장 후보 노선이 주어집니다. 가격의 합이 예산을 넘지 않는 후보 노선의 부분집합을 선택하여, 전체 승객의 총 이동 시간이 줄어드는 양을 최대로 만드세요.

이동 시간 규칙: 같은 노선에서 인접한 두 역 사이를 이동하는 데 정확히 1분이 걸리고, 한 역에서 다른 노선으로 갈아타는 데는 시간이 들지 않습니다. 모든 노선은 양방향으로 이용할 수 있습니다. 확장 전에도 현재 철도망은 이미 연결되어 있어 어떤 역에서든 다른 모든 역으로 갈 수 있습니다. 따라서 두 역 사이의 이동 시간은 두 역을 잇는 최소 역 간 이동 횟수(홉 수)와 같습니다.

첫 번째 줄에 데이터 집합의 개수 $K$가 주어집니다. 이어서 각 데이터 집합이 다음 형식으로 주어집니다.

• 첫 줄에 네 정수 $n$, $m$, $p$, $B$가 주어집니다. $n$은 역의 수($2 \le n \le 50$), $m$은 현재 노선의 수($1 \le m \le 50$), $p$는 확장 후보 노선의 수($1 \le p \le 10$), $B$는 총 예산입니다.
• 다음 $m$개의 줄은 각각 현재 노선 하나를 나타냅니다. 한 줄에는 그 노선이 지나는 역들을 순서대로 나열한 $n_i \ge 2$개의 정수가 들어 있습니다.
• 다음 $p$개의 줄은 각각 확장 후보 노선 $j$ 하나를 나타냅니다. 각 줄은 노선의 가격 $p_j$ 하나로 시작하고, 이어서 그 노선이 지나는 역들을 순서대로 나열한 $n'_j \ge 2$개의 정수가 옵니다.
• 마지막으로 $n$개의 줄이 주어지며, 각 줄에는 $n$개의 정수가 있습니다. $i$번째 줄의 $j$번째 정수는 역 $i$에서 역 $j$로 가려는 승객의 수입니다.

역의 번호는 $1$부터 $n$까지입니다.

각 데이터 집합마다 먼저 Data Set x: 를 한 줄에 출력합니다. 여기서 $x$는 데이터 집합의 번호이며 $1$부터 시작합니다. 다음 줄에는 정수 하나를 출력합니다. 가격의 합이 예산을 넘지 않는 후보 노선의 부분집합을 건설했을 때, 모든 승객의 총 이동 시간 합을 줄일 수 있는 최댓값입니다.