题目描述

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

• 地图为一张 $n$ 个点，$n-1$ 条边的简单无向连通图；
• 你初始在 $1$ 号点，该位置为空地，而其它的点要么有一个蓝宝石，要么有一个怪物；
• 你初始具有 $A$ 点攻击和 $D$ 点防御，每个蓝宝石能够给你增加一定的防御；
• 当你与怪物接触时会发生战斗，若怪物具有 $h$ 点生命、$a$ 点攻击和 $d$ 点防御，则你在此次战斗中会受到 $\left(\lceil\frac{h}{A - d}\rceil - 1\right) \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$ 防御的怪物。

输出格式

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

样例 1

输入

$0$ $6$ $5$ $3$ $1$ $2$ $1$ $3$ $1$ $4$ $2$ $5$ $3$ $6$ $2$ $15$ $20$ $3$ $2$ $10$ $10$ $4$ $1$ $2$ $1$ $1$ $1$ $1$

输出

$141$

说明

先吃掉 $4$ 号点的宝石，此时状态 $5$/$5$；再打掉 $2$ 号点的怪物，受到伤害 $105$；再吃掉 $5$ 号点的宝石，此时状态 $5$/$6$；再打掉 $3$ 号点的怪物，受到伤害 $36$；最后吃掉 $6$ 号点的宝石，此时状态 $5$/$7$。

样例 2

输入

$0$ $6$ $5$ $3$ $1$ $2$ $1$ $3$ $1$ $4$ $2$ $5$ $3$ $6$ $2$ $15$ $20$ $3$ $2$ $10$ $10$ $4$ $1$ $2$ $1$ $1$ $1$ $2$

输出

$136$

说明

先吃掉 $4$ 号点的宝石，此时状态 $5$/$5$；再打掉 $3$ 号点的怪物，受到伤害 $45$；再吃掉 $6$ 号点的宝石，此时状态 $5$/$7$；再打掉 $2$ 号点的怪物，受到伤害 $91$；最后吃掉 $5$ 号点的宝石，此时状态 $5$/$8$。

数据范围与提示

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