[AdditionalFile5274.zip](file://AdditionalFile5274.zip?type=additional_file)

#5274. 「UOI 2019 Stage 4 Day1」波托科兰迪亚的航空路线

标签: 传统 | 时间限制: 2000 ms | 内存限制: 512 MiB |

题目描述

题目译自 Ukrainian Olympiads in Informatics 2019 Stage 4 Day1 T3. Авiашляхи Потоколяндiї

最近，科扎克·武斯被选为波托科兰迪亚基础设施部的部长。波托科兰迪亚有 $n$ 座城市，编号为 $1$ 到 $n$。

目前，波托科兰迪亚的所有人都使用汽车，没有任何航空飞行。因此，基础设施部决定在波托科兰迪亚开通首批航空路线。根据国家法律，每对城市之间最多只能有一条航空路线。

已知科扎克有一个未来 $m$ 年的航空路线开通计划。他有 $m$ 个城市列表。每年，他希望从尚未使用的列表中选择一个，并在该列表中的每对尚未通过航空路线连接的城市之间开通航空连接。请注意，如果列表中的两座城市之间已经存在航空路线，则禁止再次开通。

此外，波托科兰迪亚的所有居民都知道所谓的「三个最重要的数字」：$a, b, c$。

对于每个列表 $i$，有一个重要性数值 $r_i$。已知如果开通列表 $i$ 中所有城市之间的航空连接，将为国家带来 $f(e) \cdot r_i$ 个货币单位的利润，其中 $e$ 是当年开通的新航空路线数量，而 $f(e)$ 是一个函数，定义为：$f(e) = (a \cdot e^2 + b \cdot e + c) \bmod n$（其中 $x \bmod y$ 表示 $x$ 除以 $y$ 的余数）。

科扎克·武斯在思考每年应该使用哪个列表，以便在 $m$ 年后为国家带来最大的总利润。

请帮助科扎克，找出他能为国家带来的最大货币单位数量，假设他每年可以选择一个之前未使用的列表，并在该列表中的每对尚未通过航空路线连接的城市之间开通新航空路线。

输入格式

第一行包含三个整数 $n, m, g$ $(1 \leq n \leq 10^{6}, 1 \leq m \leq 20, 0 \leq g \leq 8)$，分别表示城市数量、列表数量和子任务编号。

第二行包含三个整数 $a, b, c$ $(0 \leq a, b, c < n)$，即波托科兰迪亚的「三个最重要的数字」。

第三行包含 $m$ 个整数 $r_1, r_2, \ldots, r_m$ $(0 \leq r_i \leq 10^{6})$，表示第 $i$ 个列表的重要性。

接下来的 $m$ 行，每行包含一个整数 $s_i$ $(1 \leq s_i \leq n)$ 以及 $s_i$ 个整数 $t_{i1}, t_{i2}, \ldots, t_{is_i}$ $(1 \leq t_{ij} \leq n)$，分别表示第 $i$ 个列表中的城市数量和列表中的城市编号。保证列表中的所有数字均不同。

保证所有 $s_i$ 的总和不超过 $3 \cdot 10^{6}$。

输出格式

输出一个整数，表示科扎克能为国家带来的最大货币单位数量。

样例 1

输入

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

输出

11

在第一个样例中，可以按以下顺序使用列表：$[1, 2, 3]$。

样例 2

输入

6 4 0
1 2 3
3 2 3 4
3 4 5 6
3 1 4 5
2 1 3
3 3 4 5

输出

35

在第二个样例中，可以按以下顺序使用列表：$[2, 1, 3, 4]$。

数据范围与提示

详细子任务附加限制及分值如下表所示：