Economic Platform Assignment

This is the first problem of the yLOI series that is named after a song, although the song is not by Yin Lin. The title comes from our protagonist, Liangliang. During a subway journey in Qingdao, after meeting some friends, Liangliang—who aced physics in college though he dislikes the subject—and Fusu encounter a challenge. While riding the subway, they pass through a station named "Physics Station" and Liangliang, having just finished a high‐school physics exam, poses an economics problem to Fusu. Since Fusu cannot solve it, Liangliang decides to test you with this economic problem.

Qingdao has n metro lines and m stations. Each metro line runs at a fixed underground depth. If a metro line running at depth i passes station j, then a platform at depth i must be built at station j with a cost of \(a_{i,j}\). Note that you only need to consider the platform digging cost at the specific depth (i.e. we ignore the cost of access tunnels to the surface).

For any two lines u and v that both pass through the same station, they cannot be assigned the same depth; otherwise, the two trains would collide. If the two lines do not share any station, they are allowed to be on the same or on different depths.

Your task is to assign each metro line a depth \(d_u\) (an integer between 1 and \(n\)) in order to ensure that for every station j, all lines passing through it have different depths. The total cost is computed as follows:

[ \text{Total Cost} = \sum_{u=1}^{n} \sum_{j \in R(u)} a_{d_u, j}, ]

where \(R(u)\) is the set of stations that line u passes through. Compute the minimum total cost required so that all metro lines can operate safely without collisions.

inputFormat

The input begins with two integers (n) and (m) — the number of metro lines and the number of stations respectively.

Then, for each of the next (n) lines (for metro lines (1) through (n)), the description is as follows:\

• The first integer (k) denotes the number of stations this line passes through.\
• Followed by (k) integers listing the station indices (each between 1 and (m)).
  
  After that, there are (m) lines. The (j)th of these lines contains (n) space‐separated integers, representing the cost (a_{1,j}, a_{2,j}, \ldots, a_{n,j}) of building a platform at station (j) at depths 1 through (n) respectively.

outputFormat

Output a single integer, the minimum total cost required so that all metro lines can operate safely under the given constraints.

sample

2 2
2 1 2
1 2
3 5
4 2

9