A86031.蓝宝石魔塔

你在玩一个奇怪的魔塔，这个魔塔的设定是这样的：

• 地图为一张 $n$ 个点，$n-1$ 条边的简单无向连通图；

• 你初始在 $1$ 号点，该位置为空地，而其它的点要么有一个蓝宝石，要么有一个怪物；

• 你初始具有 $A$ 点攻击和 $D$ 点防御，每个蓝宝石能够给你增加一定的防御；

• 当你与怪物接触时会发生战斗，若怪物具有 $h$ 点生命、$a$ 点攻击和 $d$ 点防御，则你在此次战斗中会受到 $(\lceil\frac h{A-d}\rceil-1)\times(a-D)$ 点伤害。注意：这个公式与一般的魔塔有所不同，当 $D>a$ 时该伤害应为负值而不是 $0$ ，相当于给你回复相应的生命值

• 当一个非空地节点的蓝宝石被吃掉或怪物被打败时，该节点也会变成空地；

• 你可以沿着边在空地上任意穿梭，或从空地走向相连的蓝宝石节点或怪物节点并触发对应事件；

• 当所有节点都变为空地时，游戏结束。

现在，你拥有无限的生命值，他想知道游戏结束时受到的伤害总和的最小值。

第一行：一个整数 $c$ ，表示测试点编号。特殊地，样例的测试点编号为 $0$ 。

第二行：三个整数 $n$ 、$A$ 、$D$ ，分别表示节点数目、初始攻击和初始防御。

接下来的 $n-1$ 行，每行两个整数 $x_i$ 和 $y_i$ ，表示 $x_i$ 和 $y_i$ 之间有一条无向边。保证给出的是一棵树。

接下来的 $n-1$ 行，每行若干个整数，分别表示 $2\sim n$ 号节点的类型。具体地：

• 第一个数 $\text{opt}$ ，表示节点类型；
• 若 $\text{opt}=1$ ，接下来输入一个整数 $v_i$ ，表示该点处有一个增加 $v_i$ 防御的蓝宝石；若 $\text{opt}=2$ ，接下来输入三个整数 $h_i$ 、$a_i$ 、$d_i$ ，表示该点处有一个 $h_i$ 生命、$a_i$ 攻击、$d_i$ 防御的怪物。

输出一行一个整数，表示最小伤害总和。

测试点编号	$n\le$	约定
$1$	$10$
$2\sim 4$	$1000$
$5\sim 6$	$100000$	蓝宝石数目不超过 $10$
$7\sim 11$	$100000$	除 $1$ 号点外其余点度数不超过 $2$ ，且蓝宝石仅出现在叶子节点
$12\sim 16$	$100000$	除 $1$ 号点外其余点度数不超过 $2$
$17\sim 18$	$100000$
$19\sim 20$	$300000$

对于 $100\%$ 的数据，$1\le A,D,h,a,d\le 10^5$ ，$d<A$ ，$1\le v\le 10^3$ 。