给定两棵带权有根树。对于每个顶点，其子节点是有序的。你可以假设它们从左到右排列。你有四种基本操作：生长（growing）、扩展（expansion）、收缩（contraction）和重标号（relabeling）。

1. 生长：对于顶点 $x$，设其子节点列表为 $y_1, y_2, \dots, y_m$。你可以添加一个新顶点 $z$，添加一条连接 $x$ 和 $z$ 的边，并将顶点 $z$ 插入到子节点列表的第 $k$ 个位置。$x$ 的子节点列表变为 $y_1, y_2, \dots, y_{k-1}, z, y_k, y_{k+1}, \dots, y_m$。此操作的代价为 $c_1$ 乘以新边 $(x, z)$ 的权重。
2. 扩展：对于顶点 $x$，设其子节点列表为 $y_1, y_2, \dots, y_m$。你可以选择一个区间 $[l, r]$ ($1 \le l \le r \le m$)。添加一个新顶点 $z$ 作为顶点 $y_l, y_{l+1}, \dots, y_r$ 的父节点，并添加一条连接 $x$ 和 $z$ 的边。$x$ 的子节点列表变为 $y_1, y_2, \dots, y_{l-1}, z, y_{r+1}, \dots, y_m$。$z$ 的子节点列表变为 $y_l, y_{l+1}, \dots, y_r$。对于所有 $l \le i \le r$，边 $(z, y_i)$ 的权重与原树中边 $(x, y_i)$ 的权重相同。此操作的代价为 $c_1$ 乘以新边 $(x, z)$ 的权重。
3. 收缩：对于顶点 $x$，设其子节点列表为 $y_1, y_2, \dots, y_m$。你可以选择其中一个子节点 $y_k$。设 $y_k$ 的子节点列表为 $z_1, z_2, \dots, z_p$。你可以收缩边 $(x, y_k)$。操作后顶点 $y_k$ 被移除，$x$ 的子节点列表变为 $y_1, y_2, \dots, y_{k-1}, z_1, z_2, \dots, z_p, y_{k+1}, \dots, y_m$。对于所有 $1 \le i \le p$，边 $(x, z_i)$ 的权重与原树中边 $(y_k, z_i)$ 的权重相同。此操作的代价为 $c_2$ 乘以原树中边 $(x, y_k)$ 的权重。
4. 重标号：对于顶点 $x$ 及其子节点 $y$，将边 $(x, y)$ 的权重从 $w_1$ 修改为 $w_2$。此操作的代价为 $c_3 \cdot |w_1 - w_2|$。

此外还有一些特殊规则：

• 你不能对通过生长或扩展操作添加的边 $(x, z)$ 进行重标号。
• 你不能收缩已经被重标号的边。

你希望执行这些操作，将第一棵树变为第二棵树。输出执行这些操作的最小代价。

当且仅当存在一个从第一棵树的顶点到第二棵树的顶点的双射，且该双射保持根节点、子节点的顺序以及对应边的权重相同时，两棵树被认为是相同的。

输入格式

第一行包含三个整数 $c_1, c_2$ 和 $c_3$ ($1 \le c_1, c_2, c_3 \le 10^6$)，分别表示生长（或扩展）、收缩和重标号的代价。

接下来给出两棵树。 对于每棵树，第一行包含一个整数 $n$，表示顶点数量。在接下来的 $n$ 行中，每行以一个整数 $k$ 开头，表示子节点的数量，随后是 $2k$ 个整数 $c_1, w_1, \dots, c_k, w_k$ ($0 \le c_i \le 10^6$)，表示子节点列表以及到子节点的边的权重。

第一棵树的大小不超过 50。第二棵树的大小不超过 2000。

输出格式

输出答案。

样例

输入 1

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

输出 1

5