题目描述

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

• 地图为一张 $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$ 防御的怪物。

输出格式

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

样例 1

input

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

output

141

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

样例 2

input

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

output

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$ 。