题目描述

某山贼集团在绿荫村拥有强大的势力。整个绿荫村由 $n$ 个连通的小村落组成，并且保证对于每两个小村落有且仅有一条简单路径相连。将小村落从 $1$ 至 $n$ 编号，山贼集团的总部设在编号为 $1$ 的小村落中。

山贼集团除了老大坐镇总部以外，其他的 $p$ 个部门希望在村落的其他地方（洛谷注：其实也包括总部）建立分部。$p$ 个分部可以在同一个小村落中建设，也可以分别建设在不同的小村落中，在不同的村落建设不同的分部需要花费不同的费用。

每个分部到总部的路径称为这个部门的管辖范围，于是这 $p$ 个分部的管辖范围可能重叠，或者完全相同。当多个分部管辖同一个村落时，他们之间可能发生矛盾，从而损失一部分利益，也可能相互合作，从而获取一部分利益。

请注意，如果相同的分部同时管辖多个村落，那么对于每个村落，都会计算一次收益损失/获取。

现在请你编写一个程序，确定 $p$ 个分部的位置，使得山贼集团能够获得最大的收益。

输入格式

输入的第一行有两个整数，分别代表村落数 $n$ 和山贼集团部门数量 $p$。

第 $2$ 到第 $n$ 行，每行有两个整数 $x, y$，代表存在一条连接村落 $x$ 和村落 $y$ 的道路。

第 $(n + 1)$ 到第 $2n$ 行，每行 $p$ 个整数，第 $(i + n)$ 行的第 $j$ 个整数代表在第 $i$ 个村落建设第 $j$ 个部门的花费 $a_{i, j}$。

第 $(2n + 1)$ 行有一个整数，代表集团间相互影响利益的信息条数 $t$。

第 $(2n + 2)$ 行到第 $(2n + t + 1)$ 行，每行首先有一个整数 $v$，若 $v$ 为正，则表示会获得额外的收益，$v$ 为负则表示会有损失。然后有一个整数 $c$，代表涉及分部的数量。接下来有 $c$ 个整数，分别代表涉及的分部 $x_i$。本条信息的含义为若这 $c$ 个分部同时管辖某个小村落（可能同时存在其他分部管辖该村落），则会产生额外收益或损失，其数值大小为 $|v|$。

输出格式

输出一行一个整数代表最大的收益。

2 1
1 2
2 
1
1
3 1 1

5

提示

样例输入输出 1 解释

在 $2$ 号节点建立 $1$ 号分部，花费为 $1$，则分部集合 $\{1\}$ 可以管辖 $1, 2$ 两个节点，根据第一条信息，该集合每管辖一个节点会产生 $3$ 的收益，因此总共产生了 $2 \times 3 = 6$ 的收益，减去建立分部的花费，最大的收益为 $6 - 1 = 5$。可以证明不存在更优的方案。

数据规模与约定

对于 $40\%$ 的数据，保证 $1 \leq p \leq 6$。

对于 $100\%$ 的数据，保证：

• $1 \leq p \leq 12$，$1 \leq n \leq 100$。
• $1 \leq s,t \leq n$，$1 \leq a_{i, j} \leq 10^8$。
• $1 \leq t \leq 2^p$，$1 \leq |v| \leq 10^8$，$1 \leq c \leq p$，$1 \leq x_i \leq p$ 且 $x_i$ 互不相同。
• 答案的绝对值不超过 $10^8$。