[yLOI2020] 凉凉

题目背景

> 凉凉三生三世恍然如梦,须臾的年风干泪痕。 > 若是回忆不能再相认,就让情分落九尘。 > 凉凉十里何时还会春盛,又见树下一盏风存。 > 落花有意流水无情,别让恩怨爱恨凉透那花的纯,吾生愿牵尘。 ——张碧晨&杨宗纬《凉凉》

题目描述

这是 yLOI 系列竞赛中第一道以歌曲命名但歌手不是银临的题目。这道题目的歌曲和问题没什么关系,只是我们的主人公叫凉凉,于是扶苏为他选择了这首歌。 凉凉在和「七瑾在成都喝着凉茶看 jk 边咕咕边嘎嘎边哔哔边在瓦片上吭吭哧哧切企鹅」群的部分群友在青岛面基结束后,和扶苏一起乘坐地铁被七瑾送到了青岛北站。在乘坐地铁的途中,他们经过了「做物理站(错埠岭站)」,做完了高考物理的凉凉给一点都不想做物理的扶苏提了一个物理问题,扶苏不会做,所以凉凉决定考你一道经济学问题。 青岛共有 $n$ 条地铁线路和 $m$ 个地铁站点。每条线路的地铁都在地下以某一固定的深度运行,而如果某深度为 $i$ 的地铁经过了地铁站 $j$,那么地铁站 $j$ 就要在深度为 $i$ 的地方挖一个站台作为上下客口,开挖该上下客口的花费为 $a_{i,j}$。我们忽略建设上下客口通向地面的通道的费用,而只考虑在该深度建上下客口的花费。显而易见,对于线路 $u$ 和线路 $v$,如果他们都经过了同一个地铁站,那么他们线路不能处在同一深度,否则两线地铁将会相撞。而如果 $u$ 和 $v$ 不存在任何一个相同的经过站点,那么这两条线既可以处在同一高度,也可以不处在同一高度。 在这个问题中,你可以认为任何两个地铁不会在除了站点以外的行驶途中相遇,也即你无需考虑两个地铁因为行驶线路交叉而在两站点之间相遇的情况。 将站点从 $1$ 至 $m$ 编号,线路从 $1$ 至 $n$ 编号,现在给定你 $n$ 条线路的经过站点列表和在每个站点的每个深度的建站花费,请你求出让所有的地铁正常运行的最小建站花费总和。

输入输出格式

输入格式


第一行有两个整数,分别表示地铁线路的数量 $n$ 和站点个数 $m$。 第 $2$ 到第 $(n+1)$ 行,每行 $m$ 个整数,第 $(i+1)$ 行的第 $j$ 个整数表示 $a_{i,j}$。 第 $(n+2)$ 行到第 $(2n+1)$ 行,每行若干个整数,第 $(n+i+1)$ 行表示地铁 $i$ 号线的运行线路信息: >每行首先有一个整数 $c$,表示该线经过的站点个数,接下来该行有 $c$ 个互不相同的整数 $u$,依次表示该地铁经过的站点编号。

输出格式


输出一行一个整数表示答案。

输入输出样例

输入样例 #1

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

输出样例 #1

10

说明

### 样例 1 解释 $1$ 号线和 $2$ 号线都经过了站点 $1$,因此他们不能处于同一深度。 令 $1$ 号线在深度 $2$ 运行,$2$ 号线在深度 $1$ 运行,则需要修建站点 $1$ 的深度 $1$ 、 $2$ 的上下客口(花费为 $4+4=8$),站点 $2$ 的深度为 $2$ 的上下客口(花费为 $1$),站点 $3$ 的深度为 $1$ 的上下客口(花费为 $1$),总花费为 $10$。可以证明,这是最优的方案。 ### 数据规模与约定 本题共 $20$ 个测试点,每个测试点 $5$ 分。 - 对于 $5\%$ 的数据,保证 $n=1$。 - 对于 $35\%$ 的数据,保证 $n,m \le 6$。 - 对于 $70\%$ 的数据,保证 $n \le 10$。 - 对于 $100\%$ 的数据,保证 $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$。 ### 提示 本题共有两个附加样例文件,见附加文件中的 cold.zip。 (本来有个更大的样例,但是因为附件不让传这么大的,就被删掉了)