Super Pipes and Ant Feeding

Bobi gets up every morning and feeds his pet ants. The ants live in a terrarium with a pipe system. The pipe system is a tree with $N$ nodes, and each pipe is one edge of the tree. The root of the tree is node 1. Because of gravity, liquid flows only from a parent node to its children.

Every pipe has a flow $X_i$, the percentage of the liquid that arrives at the parent node and goes through that pipe to the child node. For example, if 12 liters of liquid arrive at node 1 and two pipes lead out of it, one with flow 30 and one with flow 70, the child behind the first pipe gets 3.6 liters and the child behind the second pipe gets 8.4 liters. The flows of the pipes leaving the same node always add up to 100.

Some of Bobi's pipes are not regular pipes. They are super pipes, and they have the superpower of squaring the amount of liquid that goes through them. In the example above, if the pipe with flow 30 is a super pipe and its superpower is on, that child gets $3.6^2 = 12.96$ liters while the other child still gets 8.4 liters. More liquid then leaves the node than entered it. That is exactly why they are called super pipes.

Bobi can turn the superpower of each super pipe on or off. A super pipe with its superpower off behaves like a regular pipe.

The ants live only in the nodes without children, the leaves. To feed all the ants in leaf $i$, that leaf must receive at least $K_i$ liters. Bobi feeds the ants by pouring $L$ liters of liquid into the root. He does not have much money, so he wants to buy as little liquid as possible. Find the smallest $L$ for which every leaf receives the amount it needs.

In the given data the answer $L$ never exceeds $2 \cdot 10^9$.

The first line contains the integer $N$, the number of nodes ($1 \le N \le 1000$).

Each of the next $N - 1$ lines contains four integers $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$ and $B_i$ are the two nodes joined by a pipe, $X_i$ is the flow of that pipe, and $T_i$ says whether the pipe is a super pipe. If $T_i$ is 1 the pipe is a super pipe, and if $T_i$ is 0 it is a regular pipe. Liquid flows away from node 1, so the endpoint closer to node 1 is the parent. The $N - 1$ pipes form a tree.

The last line contains $N$ integers $K_i$. If node $i$ is a leaf, $K_i$ is an integer between 1 and 10. Otherwise $K_i$ is $-1$.

Print the smallest amount of liquid Bobi has to pour into the root, rounded to three decimal places, on one line. Always write three digits after the decimal point. For example, if the answer is exactly 8, print 8.000.