小 Bobi 每天早上起床后都会喂养他最喜欢的宠物：蚂蚁。他把它们养在一个玻璃容器中，容器里有一个管道系统，可以用一棵拥有 $N$ 个节点的树来表示。管道由树的边表示。树的根节点为节点 1。在管道系统内部，由于重力的作用，液体从父节点流向其子节点。

我们知道每条管道的流量比例 $X_i$：即从父节点流经该管道到达子节点的液体占父节点总液体的百分比。让我们观察以下例子：

图中节点 1 含有 12 升液体，其下方连接着两条管道。其中一条的流量比例为 $X_i = 30$，另一条为 $X_i = 70$。节点 2 将获得 3.6 升液体，节点 3 将获得 8.4 升液体。在输入数据中，从同一个节点出发的所有管道的流量比例之和总是等于 100。

Bobi 的一些管道不仅仅是普通管道，它们有点奇怪。它们是“超级管道”，拥有将其流过的液体量进行平方的超能力。在前面的例子中，如果第一条管道拥有超能力，那么节点 2 将获得 12.96 升液体，而节点 3 仍然只获得 8.4 升液体。请注意，此时一个节点流出的液体量比流入它的液体量还要多。这正是这些管道被称为超级管道的原因！

所有超级管道的超能力都可以被 Bobi 开启或关闭。

蚂蚁只居住在树的叶子节点（即没有任何子节点的节点）中。对于每个叶子节点，我们知道喂饱居住在该叶子节点中的所有蚂蚁所需的液体量 $K_i$。Bobi 想通过向树根倒入 $L$ 升液体来喂养他的蚂蚁。他没有太多钱，所以他想知道为了让所有蚂蚁都吃饱，他需要购买的液体的最小升数。

请注意：输入数据保证所需的数量 $L$ 不会超过 $2 \cdot 10^9$。

输入格式

输入的第一行包含整数 $N$（$1 \le N \le 1000$）。

接下来的 $N - 1$ 行，每行包含四个整数 $A_i, B_i, X_i, T_i$（$1 \le A_i, B_i \le N$，$1 \le X_i \le 100$，$0 \le T_i \le 1$），其中 $A_i$ 和 $B_i$ 是管道的两端（由管道连接的节点编号），$X_i$ 是流经该管道的液体流量比例，$T_i$ 表示该管道是否具有超能力。如果 $T_i$ 为 1，则该管道具有超能力，否则没有。

下一行包含 $N$ 个整数 $K_i$，描述第 $i$ 个节点中蚂蚁所需的液体量。如果第 $i$ 个节点不是叶子节点，则 $K_i$ 为 -1，否则它将是区间 $[1, 10]$ 内的一个整数。

输出格式

输出的第一行也是唯一的一行必须包含题目所要求的数值。

请注意：与正确（精确）答案允许的绝对误差为 $0.001$。

样例

输入样例 1

5
1 2 50 0
1 3 50 0
2 4 25 0
2 5 75 1
-1 -1 4 1 9

输出样例 1

8.00

输入样例 2

3
1 2 20 1
1 3 80 1
-1 4 8

输出样例 2

10.0000

输入样例 3

6
1 2 100 1
2 3 20 0
2 4 20 0
2 5 60 0
4 6 100 1
-1 -1 1 -1 1 2

输出样例 3

2.659

说明

第一个样例的解释：如果 Bobi 向树根倒入 8 升液体，节点 3 将获得 4 升，节点 4 将获得 1 升，节点 5 将获得 9 升。这些节点都是叶子节点（里面有蚂蚁），这正是蚂蚁需要获得的精确最小量。此外，8 升是满足“蚂蚁”条件的最小液体量。