← 返回题目列表

Codeforces · 1408/E

E. 避免彩虹自行车

中文机器翻译题面 查看原题

给你 $$$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\}$$$.

我们将得到图表:

其中没有彩虹循环。