A6006. 蓝宝石魔塔

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

- 地图为一张 $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$ 。