Description

This is the first problem in the yLOI series that is named after a song whose singer is not Yinlin. The song has little to do with the problem; it is just that our protagonist is called “Liangliang”, so Fusu chose this song for him.

After Liangliang met up in Qingdao with some friends from the group “Qijin in Chengdu drinking cold tea watching jk while cooing and quacking and chattering while clanking and chopping penguins on tiles”, he took the subway with Fusu and was seen off by Qijin to Qingdao North Railway Station. During the subway ride, they passed “Zuowuli Station (Cuobuling Station)”. Having just finished doing Gaokao physics, Liangliang asked Fusu, who did not want to do physics at all, a physics question. Fusu could not solve it, so Liangliang decided to test you with an economics problem.

Qingdao has $n$ subway lines and $m$ subway stations. The trains of each line run underground at a fixed depth. If a subway line at depth $i$ passes through station $j$, then station $j$ must dig a platform at depth $i$ as the boarding/alighting access, and the cost of digging this access is $a_{i,j}$. We ignore the cost of building the passage from the access to the ground, and only consider the cost of building the access at that depth. Obviously, for lines $u$ and $v$, if they both pass through the same station, then they cannot be at the same depth; otherwise, the two lines will collide. If $u$ and $v$ do not share any station, then they may be at the same depth or at different depths.

In this problem, you may assume that any two subways will not meet during travel except at stations; that is, you do not need to consider the case where two subways meet between two stations due to intersecting tracks.

Stations are numbered from $1$ to $m$, and lines are numbered from $1$ to $n$. You are now given the list of stations each of the $n$ lines passes through and the construction cost at each station for each depth. Please find the minimum total construction cost so that all subways can operate normally.

Input Format

The first line contains two integers, denoting the number of subway lines $n$ and the number of stations $m$.
Lines $2$ to $(n+1)$ each contain $m$ integers; the $j$-th integer in line $(i+1)$ denotes $a_{i,j}$.
Lines $(n+2)$ to $(2n+1)$ each contain several integers; line $(n+i+1)$ describes the route information of line $i$:

Each line first contains an integer $c$, denoting the number of stations this line passes through. Then the line contains $c$ distinct integers $u$, in order, denoting the station numbers that this subway passes through.

Output Format

Output one line with one integer, the answer.

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

10

Hint

Sample 1 Explanation

Line $1$ and line $2$ both pass through station $1$, so they cannot be at the same depth.
Let line $1$ run at depth $2$ and line $2$ run at depth $1$. Then we need to build the boarding/alighting accesses at station $1$ for depths $1$ and $2$ (cost $4+4=8$), the access at station $2$ for depth $2$ (cost $1$), and the access at station $3$ for depth $1$ (cost $1$), for a total cost of $10$. It can be proved that this is optimal.

Constraints

There are $20$ test points in total, each worth $5$ points.

• For $5\%$ of the testdata, it is guaranteed that $n=1$.
• For $35\%$ of the testdata, it is guaranteed that $n,m \le 6$.
• For $70\%$ of the testdata, it is guaranteed that $n \le 10$.
• For $100\%$ of the testdata, it is guaranteed that $1 \le n \le 14$, $1 \le m \le 10^5$, $1 \le a_{i,j} \le 10^9$, $1 \le c,u \le m$.

Notes

This problem provides two additional sample files; see cold.zip in the attachments.

(There was originally a larger sample, but it was deleted because the attachment does not allow uploading such a large file.)

Translated by ChatGPT 5