题目描述

档案馆管理员林澈正在整理两份树形手稿。每份手稿都是一棵有根树，每条边带有一个权值；并且对于每个点，它的所有儿子都有从左到右的顺序。林澈希望把第一份手稿修改成第二份手稿，修改时可以使用四种基本操作。

生长

对于一个点 $x$，设它当前的儿子序列为

$$y_1,y_2,\ldots,y_m.$$

可以新建一个点 $z$，在 $x$ 与 $z$ 之间连一条边，并把 $z$ 插入到儿子序列的第 $k$ 个位置，使得 $x$ 的儿子序列变为

$$y_1,y_2,\ldots,y_{k-1},z,y_k,y_{k+1},\ldots,y_m.$$

该操作的代价为 $c_1$ 乘以新边 $(x,z)$ 的权值。

展开

对于一个点 $x$，设它当前的儿子序列为

$$y_1,y_2,\ldots,y_m.$$

可以选择一个区间 $[l,r]$，满足 $1\le l\le r\le m$。新建一个点 $z$ 作为 $y_l,y_{l+1},\ldots,y_r$ 的父亲，并在 $x$ 与 $z$ 之间连一条边。修改后，$x$ 的儿子序列变为

$$y_1,y_2,\ldots,y_{l-1},z,y_{r+1},\ldots,y_m,$$

而 $z$ 的儿子序列变为

$$y_l,y_{l+1},\ldots,y_r.$$

对所有 $l\le i\le r$，新边 $(z,y_i)$ 的权值等于原树中边 $(x,y_i)$ 的权值。该操作的代价为 $c_1$ 乘以新边 $(x,z)$ 的权值。

收缩

对于一个点 $x$，设它当前的儿子序列为

$$y_1,y_2,\ldots,y_m.$$

可以选择其中一个儿子 $y_k$。设 $y_k$ 的儿子序列为

$$z_1,z_2,\ldots,z_p.$$

收缩边 $(x,y_k)$ 后，点 $y_k$ 被删除，$x$ 的儿子序列变为

$$y_1,y_2,\ldots,y_{k-1},z_1,z_2,\ldots,z_p,y_{k+1},\ldots,y_m.$$

对所有 $1\le i\le p$，新边 $(x,z_i)$ 的权值等于原树中边 $(y_k,z_i)$ 的权值。该操作的代价为 $c_2$ 乘以原边 $(x,y_k)$ 的权值。

重标权值

对于一个点 $x$ 及其一个儿子 $y$，可以把边 $(x,y)$ 的权值从 $w_1$ 改为 $w_2$。该操作的代价为

$$c_3\cdot |w_1-w_2|.$$

此外还有两条特殊规则：

• 由生长或展开操作中新加入的边 $(x,z)$ 不能再被重标权值；
• 已经被重标权值的边不能再被收缩。

两棵树相同，当且仅当存在一个点之间的双射，使得根对应根，儿子的左右顺序保持一致，并且对应边的权值完全相同。

请你求出把第一棵树修改为第二棵树的最小总代价。

输入格式

第一行包含三个整数 $c_1,c_2,c_3$，分别表示生长或展开、收缩、重标权值三类代价系数。

接下来依次给出两棵树。

对于每棵树，第一行包含一个整数 $n$，表示点数。接下来 $n$ 行描述这棵树，第 $i$ 行先包含一个整数 $k$，表示点 $i$ 的儿子数量；随后包含 $2k$ 个整数：

$$v_1,w_1,v_2,w_2,\ldots,v_k,w_k,$$

表示点 $i$ 的儿子从左到右依次为 $v_1,v_2,\ldots,v_k$，且边 $(i,v_j)$ 的权值为 $w_j$。

输入保证每份描述都是一棵有根树；根为唯一没有父亲的点。

输出格式

输出一行一个整数，表示最小总代价。

数据范围

• $1\le c_1,c_2,c_3\le 10^6$；
• 边权满足 $0\le w_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

输出

5