19021번 - Edit 다국어

문제

You are given two weighted rooted trees. For each vertex, the children are ordered. You can assume they are arranged from left to right. You have four elementary operations: growing, expansion, contraction, and relabeling.

1. Growing: For a vertex $x,ドル let the children list be $y_1, y_2, \ldots, y_m$. You can add a new vertex $z,ドル add an edge between $x$ and $z,ドル and insert the vertex $z$ to the $k$-th position in the children list. The children list of $x$ becomes $y_1, y_2, \ldots, y_{k-1}, z, y_k, y_{k+1}, \ldots, y_m$. The cost of this operation is $c_1$ times the weight of the new edge $(x, z)$.
2. Expansion: For a vertex $x,ドル let the children list be $y_1, y_2, \ldots, y_m$. You can choose an interval $[l, r]$ (1ドル \leq l \leq r \leq m$). Add a new vertex $z$ as the parent of vertices $y_l, y_{l+1}, \ldots, y_r,ドル and an edge between $x$ and $z$. The children list of $x$ becomes $y_1, y_2, \ldots, y_{l-1}, z, y_{r+1}, \ldots, y_m$. The children list of $z$ becomes $y_l, y_{l+1}, \ldots, y_r$. For all $l \leq i \leq r,ドル the weight of the edge $(z, y_i)$ is the same as the edge $(x, y_i)$ in the original tree. The cost of this operation is $c_1$ times the weight of the new edge $(x, z)$.
3. Contraction: For a vertex $x,ドル let the children list be $y_1, y_2, \ldots, y_m$. You can choose one of its children $y_k$. Let the children list of $y_k$ be $z_1, z_2, \ldots, z_p$. You can contract the edge $(x, y_k)$. The vertex $y_k$ is removed after this operation. And the children list of $x$ becomes $y_1, y_2, \ldots, y_{k-1}, z_1, z_2, \ldots, z_p, y_{k+1}, \ldots, y_m$. For all 1ドル \leq i \leq p,ドル the weight of the edge $(x, z_i)$ is the same as the edge $(y_k, z_i)$ in the original tree. The cost of this operation is $c_2$ times the weight of the edge $(x, y_k)$ in the original tree.
4. Relabeling: For a vertex $x$ and one of its children $y,ドル change the weight of edge $(x, y)$ from $w_1$ to $w_2$. The cost of this operation is $c_3 \cdot |w_1 - w_2|$.

There are also some special rules:

• You can not relabel an edge which is the $(x, z)$ edge added by growing or expansion operation.
• You can not contract an edge which was relabeled.

You want to perform these operations, and change the first tree into the second tree. Output the minimum cost of doing so.

Two trees are considered the same if and only if there is a bijection from the vertices of the first tree to the vertices of the second tree that preserves the root and the order of children, and the weights of corresponding edges are the same.

입력

The first line contains three integers $c_1,ドル $c_2,ドル and $c_3$ (1ドル \leq c_1, c_2, c_3 \leq 10^6$) indicating the cost of growing (or expansion), contraction, and relabeling, respectively.

Next, the two trees are given.

For each tree, the first line contains an integer $n$ indicating the number of vertices. In the following $n$ lines, each line starts an with integer $k$ indicating the number of children, followed by 2ドル k$ integers $c_1, w_1, \ldots, c_k, w_k$ (0ドル \leq c_i \leq 10^6$) indicating the children list and the weights of edges to children.

The size of the first tree will not be greater than 50ドル$. The size of the second tree will not be greater than 2000ドル$.

출력

Output the answer.

제한

힌트