图论一顿套模板

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

路哥今天被崛北吩咐去买东西,然而依照路哥的强大,肯定希望能花费最少的钱。路哥可以用自己的技能把一些比较便宜的原料合成所需要的东西。(路哥就是这么强大,合成费用是忽略不记的)那么路哥最少要花费多少钱,才能完成任务呢?

Input

第一行输入两个以空格分隔的整数 $n$, $m$。分别表示路哥需要买的物品的数量和这 $n$ 个物品可能需要的 $m$ 个原材料。

接下来一行输入 $n$ 个整数 $a[i]$,表示买第 $i$ 个物品所需要的钱数(标号从 $1$ 到 $n$)。

接下来一行输入 $m$ 个整数 $b[i]$,表示买第 $i$ 个原材料所需要的钱数(标号从 $1$ 到 $m$)。

接下来 $n$ 行,每行首先输入一个整数 $k[i]$,表示合成第 $i$(从 $1$ 到 $n$)个物品所需要的原材料的数量。然后输入 $k$ 个整数(每个整数范围为 $[1, m]$),表示需要的原材料的标号。

注意:原材料买一次可以多次使用。

$(1 \leqslant n, m \leqslant 500)$

$(1 \leqslant a[i], b[i] \leqslant  1000)$

$(1 \leqslant k[i] \leqslant m)$

Output

输出一个整数,表示路哥买完所有物品所需要的最少钱数。

Sample Input

3 3
10 8 6
9 6 7
3 1 2 3
1 1
1 1

Sample Output

19

Hint

Source

【2016级ACM暑假集训 结训赛(算法组)】UMR