化学家们刚刚构思出了一大类名为 NeoMole 的分子。这些分子极其出色的性质使其成为治疗当前流行性感冒肺炎的潜在药物。

从理论上讲，一个 NeoMole 分子仅由一种化学元素——氖（neonium）组成。在 NeoMole 分子中，氖原子通过常规化学键连接。与碳不同的是，连接到一个氖原子的化学键数量竟然是无限的。此外，分子结构是无环的。

科学家们希望使用小的 NeoMole 分子作为底物（即原材料）来合成一些 NeoMole 分子。为了合成大分子，可以选择两个分子（可以是底物，也可以是之前合成的分子），并为每个分子指定一个原子。经过一些神秘的化学反应后，指定的原子之间会形成一个新的化学键。

图 1：样例测试用例 1 的最优合成方案。

由于 NeoMole 非常珍贵，科学家们希望最小化他们在底物上的总成本。你能编写一个程序来帮助他们找到最优的合成方案吗？不要错过赚大钱的机会！

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 500$)，表示要合成的分子中的原子数量。原子编号为 $1$ 到 $n$。接下来有 $n - 1$ 行，每行包含两个整数 $u, v$ ($1 \le u, v \le n$)，表示第 $u$ 个原子和第 $v$ 个原子之间存在化学键。

接下来一行包含一个整数 $m$ ($1 \le m \le 200$)，表示底物的数量。输入剩余部分指定了这些底物分子。每个底物分子的说明以一行包含两个整数 $n, c$ ($1 \le n \le 500, 1 \le c \le 10^6$) 开始，分别表示分子中的原子数量和每个拷贝的成本。随后是 $n - 1$ 行，以与上述相同的方式指定分子间的化学键。保证所有底物分子中的原子总数不超过 $500$。在合成过程中，你可以使用任意数量的任何底物分子。

保证在所有分子中，原子都是无环连接的。

输出格式

输出一行整数，表示原材料的最小总成本。如果无法合成目标分子，则输出 impossible。

样例

输入 1

8
1 2
2 3
2 4
4 5
4 6
6 7
6 8
3
3 2
1 2
2 3
2 3
1 2
1 5

输出 1

7

输入 2

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

输出 2

impossible