给你 $$$m$$$ 组整数 $$$A_1, A_2, \ldots, A_m$$$;这些集合的元素是介于 $$$1$$$ 和 $$$n$$$(含)之间的整数。
有两个正整数数组 $$$a_1, a_2, \ldots, a_m$$$ 和 $$$b_1, b_2, \ldots, b_n$$$。
在一次操作中,您可以从集合 $$$A_i$$$ 中删除一个元素 $$$j$$$ 并为此支付 $$$a_i + b_j$$$ 硬币。
您可以进行多次(也许没有)操作(某些集合可能会变空)。
之后,您将制作一个由 $$$n$$$ 个顶点组成的边颜色无向图。对于每个集合 $$$A_i$$$,您将为 A_i$$$ 中的所有 $$$x、y \in 和 $$$x < y$$$ 添加一条颜色为 $$$i$$$ 的边 $$$(x, y)$$$。某些顶点对可以与多个边连接,但这些边具有不同的颜色。
如果一个循环 $$$i_1 \to e_1 \to i_2 \to e_2 \to \ldots \to i_k \to e_k \to i_1$$$ ($$$e_j$$$ 是该图中连接顶点 $$$i_j$$$ 和 $$$i_{j+1}$$$ 的一些边),如果其上的所有边都有不同的颜色,则称为彩虹。
求出获得没有彩虹循环的图表所需支付的最少硬币数量。
输入
第一行包含两个整数 $$$m$$$ 和 $$$n$$$ ($$$1 \leq m, n \leq 10^5$$$)、图中的集合数和顶点数。
第二行包含 $$$m$$$ 整数 $$$a_1, a_2, \ldots, a_m$$$ ($$$1 \leq a_i \leq 10^9$$$)。
第三行包含 $$$n$$$ 整数 $$$b_1, b_2, \ldots, b_n$$$ ($$$1 \leq b_i \leq 10^9$$$)。
在接下来的 $$$m$$$ 行中都有集合的描述。在第 $$$i$$$ 行中,第一个整数 $$$s_i$$$ ($$$1 \leq s_i \leq n$$$) 等于 $$$A_i$$$ 的大小。然后$$$s_i$$$ 整数如下:集合$$$A_i$$$ 的元素。这些整数从 $$$1$$$ 到 $$$n$$$ 并且不同。
保证所有 $$$1 \leq i \leq m$$$ 的 $$$s_i$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
打印一个整数:为避免所获得的图中出现彩虹循环而应支付的操作的最小硬币数量。
示例
输入 #1
3 2 1 2 3 4 5 2 1 2 2 1 2 2 1 2
输出 #1
11
输入 #2
7 8 3 6 7 9 10 7 239 8 1 9 7 10 2 6 239 3 2 1 3 2 4 1 3 1 3 7 2 4 3 5 3 4 5 6 7 2 5 7 1 8
输出 #2
66
注意
第一次测试时,可以进行这样的操作:
- 从集合 $$$1$$$ 中删除元素 $$$1$$$。您应该为此支付 $$$a_1 + b_1 = 5$$$ 硬币。
- 从集合 $$$2$$$ 中删除元素 $$$1$$$。您应该为此支付 $$$a_2 + b_1 = 6$$$ 硬币。
您总共支付 $$$11$$$ 硬币。经过这些操作后,第一组和第二组将等于 $$$\{2\}$$$,第三组将等于 $$$\{1, 2\}$$$。
因此,该图将由颜色为 $$$3$$$ 的一条边 $$$(1, 2)$$$ 组成。
在第二次测试中,可以进行这样的操作:
- 从集合 $$$1$$$ 中删除元素 $$$1$$$。您应该为此支付 $$$a_1 + b_1 = 11$$$ 硬币。
- 从集合 $$$2$$$ 中删除元素 $$$4$$$。您应该为此支付 $$$a_2 + b_4 = 13$$$ 硬币。
- 从集合 $$$3$$$ 中删除元素 $$$7$$$。您应该为此支付 $$$a_3 + b_7 = 13$$$ 硬币。
- 从集合 $$$4$$$ 中删除元素 $$$4$$$。您应该为此支付 $$$a_4 + b_4 = 16$$$ 硬币。
- 从集合 $$$6$$$ 中删除元素 $$$7$$$。您应该为此支付 $$$a_6 + b_7 = 13$$$ 硬币。
您总共支付 $$$66$$$ 硬币。
在这些操作之后,集合将是:
- $$$\{2, 3\}$$$;
- $$$\{1\}$$$;
- $$$\{1, 3\}$$$;
- $$$\{3\}$$$;
- $$$\{3, 4, 5, 6, 7\}$$$;
- $$$\{5\}$$$;
- $$$\{8\}$$$.
我们将得到图表:
其中没有彩虹循环。