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:

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 \le N \le 1000)~.

Each of the following ~N-1~ lines contain 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)~ 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~.

Sample Input 1

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

Sample Output 1

8.00

Explanation for Sample Output 1

If Bobi pours 8 liters of liquid into the root of the tree, node 3 will get 4 liters, node 4 will get 1 liter and node 5 will get 9 liters. These nodes are leaves (they have ants in them) and this is the exact minimum amount the ants need to get. Also, 8 liters is the minimum amount of liquid that satisfies the "ant" conditions.

Sample Input 2

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

Sample Output 2

10.0000

Sample Input 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

Sample Output 3

2.659