Network Expansion

A city is expanding its public rail network. Several expansion routes are being considered, but the budget is limited, so only some of them can be built. Your task is to choose the affordable subset of proposed routes that reduces the total passenger travel time as much as possible.

You are given the current rail system and up to 10 proposed expansion routes. Choose a subset of the proposed routes whose total price does not exceed the budget so that the total travel time of all passengers is reduced by the largest possible amount.

Travel-time model: riding from one station to an adjacent station on any route takes exactly one minute, and transferring between routes at a shared station is instantaneous. Every route can be traveled in both directions. Even before any expansion the current system is already connected, so every station is reachable from every other station. The travel time between two stations is therefore the minimum number of station-to-station hops between them.

The first line contains the number of data sets $K$. Each data set then follows in this form:

• The first line contains four integers $n$, $m$, $p$, and $B$: the number of stations $n$ ($2 \le n \le 50$), the number of current routes $m$ ($1 \le m \le 50$), the number of proposed expansion routes $p$ ($1 \le p \le 10$), and the total budget $B$.
• The next $m$ lines each describe one current route. A route line lists $n_i \ge 2$ integers: the stations the route visits, in order.
• The next $p$ lines each describe one proposed expansion route $j$. Such a line starts with one integer $p_j$, the price of the route, followed by $n'_j \ge 2$ integers giving the stations the route visits, in order.
• Finally, $n$ lines follow, each with $n$ integers. The $j$-th integer on the $i$-th of these lines is the number of passengers who want to travel from station $i$ to station $j$.

Stations are numbered from $1$ to $n$.

For each data set, output a line Data Set x:, where $x$ is the data set number (starting at $1$). On the next line, output a single integer: the maximum total reduction in the sum of all passengers' travel times that can be achieved by building a subset of the proposed routes whose combined price does not exceed the budget.