Problem C
Mravi

Little Bobi gets up every morning and feeds his favourite pets: ants. He keeps them in a terrarium with a pipe system that can be represented as a tree with $N$ nodes. The pipes are represented by the edges of the tree. The root of the tree is located at node denoted with 1. Inside the pipe system, the liquid flows from a node to its children because of gravity.

We know the flow $X_ i$ of each pipe: the percent of fluid from the parent node that flows through that pipe to the child node. Let’s observe the following example:

Figure 1: Example

Node 1 from the image has 12 liters of liquid in it and has two pipes after it. One has the flow of $X_ i = 30$, and the other $X_ i = 70$. Node 2 is going to get $3.6$ liters and node 3 gets $8.4$ liters. In the input data, the sum of flows of pipes going from the same node will always be equal to $100$.

Some of Bobi’s pipes aren’t just regular pipes; they are a bit strange. They are super pipes that have the superpower to square the amount of liquid flowing through them. In the previous example, if the first pipe has the superpower, node 2 gets $12.96$ liters and node 3 still gets only $8.4$ liters. Notice now that a node has more liquid leaving it than the amount entering it. This is exactly the reason why these pipes are super pipes!

All super pipes can have their superpower turned on or off by Bobi.

The ants live only in the leaves of the tree (nodes that don’t have any children). For each leaf we know the required amount of liquid $K_ i$ to feed all ants living in that leaf. Bobi wants to feed his ants by pouring $L$ liters of liquid into the root of the tree. He doesn’t have much money so he wants to know the minimum amount of liters of liquid he needs to buy to keep all of his ants fed.

Please note: The input data is such that the required number $L$ will not exceed $2 \cdot 10^9$.

Input

The first line of input contains the integer $N$ ($1 \leq N \leq 1\, 000$).

Each of the following $N - 1$ lines contain four integers $A_ i$, $B_ i$, $X_ i$, $T_ i$ ($1 \leq A_ i, B_ i \leq N$, $1 \leq X_ i \leq 100$, $0 \leq T_ i \leq 1$) where $A_ i$ and $B_ i$ are the ends of a pipe (the labels of nodes connected by the pipe), $X_ i$ is the flow of the liquid through the pipe, and $T_ i$ denotes whether the pipe has a superpower. If $T_ i$ is 1, that pipe has a superpower, otherwise it does not.

The following line contains $N$ integers $K_ i$ describing the amount of liquid needed for the ants in the $i$-th node. If the $i$-th node is not a leaf, $K_ i$ will be $-1$, otherwise it will be an integer from the interval $[1, 10]$.

Output

The first and only line of output must contain the required number from the task. Please note: The allowed absolute error from the correct (precise) solution is $0.001$.

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

8.00

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

10.0000

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

2.659