题目描述

给定一个包含 $N$ 个顶点（顶点 $1,2,\ldots,N$）的简单无向图 $G$ 和 $H$。$G$ 有 $M_G$ 条边，第 $i$ 条边（$1\leq i\leq M_G$）连接顶点 $u_i$ 和顶点 $v_i$。$H$ 有 $M_H$ 条边，第 $i$ 条边（$1\leq i\leq M_H$）连接顶点 $a_i$ 和顶点 $b_i$。

你可以对图 $H$ 重复进行如下操作任意次（可以为 $0$ 次）：

• 选择一组整数 $(i,j)$，满足 $1\leq i<j\leq N$。支付 $A_{i,j}$ 日元，如果顶点 $i$ 和顶点 $j$ 之间没有边，则添加一条边；如果已经有边，则删除该边。

请你求出，为了使 $G$ 和 $H$ 同构，至少需要支付多少日元。

什么是简单无向图？简单无向图是指不包含自环和重边，且边没有方向的图。

什么是图的同构？对于 $N$ 个顶点的图 $G$ 和 $H$，如果存在一个排列 $(P_1,P_2,\ldots,P_N)$，使得对于任意 $1\leq i<j\leq N$，有：

• 当且仅当 $G$ 中存在连接顶点 $i$ 和顶点 $j$ 的边时，$H$ 中存在连接顶点 $P_i$ 和顶点 $P_j$ 的边，

则称 $G$ 和 $H$ 是同构的。

输入格式

输入以如下格式从标准输入读入。

$N$ $M_G$
$u_1$ $v_1$
$u_2$ $v_2$
$\vdots$
$u_{M_G}$ $v_{M_G}$
$M_H$
$a_1$ $b_1$
$a_2$ $b_2$
$\vdots$
$a_{M_H}$ $b_{M_H}$
$A_{1,2}$ $A_{1,3}$ $\ldots$ $A_{1,N}$ $A_{2,3}$ $\ldots$ $A_{2,N}$
$\vdots$
$A_{N-1,N}$

输出格式

请输出答案。

样例 1

输入

5
4
1 2
2 3
3 4
4 5
4
1 2
1 3
1 4
1 5
3 1 4 1
5 9 2
6 5
3

输出

9

样例 2

输入

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

输出

3

样例 3

输入

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

输出

5

样例 4

输入

2
0
0
371

输出

0

样例 5

输入

8
13
1 8
5 7
4 6
1 5
7 8
1 6
1 2
5 8
2 6
5 6
6 7
3 7
4 8
15
3 5
1 7
4 6
3 8
7 8
1 2
5 6
1 6
1 5
1 4
2 8
2 6
2 4
4 7
1 3
7483 1694 5868 3296 9723 5299 4326
5195 4088 5871 1384 2491 6562
1149 6326 2996 9845 7557
4041 7720 1554 5060
8329 8541 3530
4652 3874
3748

输出

21214

说明/提示

数据范围

• $1\leq N\leq 8$
• $0\leq M_G\leq\dfrac{N(N-1)}{2}$
• $0\leq M_H\leq\dfrac{N(N-1)}{2}$
• $1\leq u_i<v_i\leq N\ (1\leq i\leq M_G)$
• $(u_i,v_i)\neq(u_j,v_j)\ (1\leq i<j\leq M_G)$
• $1\leq a_i<b_i\leq N\ (1\leq i\leq M_H)$
• $(a_i,b_i)\neq(a_j,b_j)\ (1\leq i<j\leq M_H)$
• $1\leq A_{i,j}\leq 10^6\ (1\leq i<j\leq N)$
• 输入均为整数

样例解释 1

给定的图如下所示。

例如，可以对 $H$ 依次进行如下 $4$ 次操作，支付 $9$ 日元使 $G$ 和 $H$ 同构：

• 以 $(i,j)=(1,3)$ 进行操作。$H$ 中有顶点 $1$ 和 $3$ 的边，支付 $1$ 日元将其删除。
• 以 $(i,j)=(2,5)$ 进行操作。$H$ 中没有顶点 $2$ 和 $5$ 的边，支付 $2$ 日元将其添加。
• 以 $(i,j)=(1,5)$ 进行操作。$H$ 中有顶点 $1$ 和 $5$ 的边，支付 $1$ 日元将其删除。
• 以 $(i,j)=(3,5)$ 进行操作。$H$ 中没有顶点 $3$ 和 $5$ 的边，支付 $5$ 日元将其添加。

操作后，$H$ 如下所示。

无法用 $8$ 日元或更少使 $G$ 和 $H$ 同构，因此输出 9。

样例解释 2

例如，依次对 $(i,j)=(2,3),(2,4),(3,4)$ 进行 $3$ 次操作即可使 $G$ 和 $H$ 同构。

样例解释 3

例如，仅对 $(i,j)=(4,5)$ 进行 $1$ 次操作即可使 $G$ 和 $H$ 同构。

样例解释 4

$G$ 和 $H$ 也可能都没有边。也有可能不需要进行任何操作。

由 ChatGPT 4.1 翻译