Wesley recently bought a resort comprised of ~N~ cabins, numbered from ~1~ to ~N~. He needs to distribute water to his ~N~ cabins, with different requirements ~R_i~ per cabin. Wesley doesn't care if any cabin gets more than the required amount of water, as long as they get at least ~R_i~ units.

At each cabin there is a lever, each of which produce a different output rate ~X_i~, meaning that ~X_i~ units of water flow into cabin ~i~ if the lever is held for one second.

The cabins are connected by a network of ~N - 1~ pipes. Wesley resides in cabin ~1~, the head cabin, and due to some interesting properties of the land around him, water always flows away from the head cabin.

Each pipe has a flow rate ~F_i~. When ~Y~ units of water flows into a node, each connected pipe that leads away from the head cabin transfers ~F_i \times Y~ units of water into the adjacent cabin. Any water not moved into adjacent cabins is kept in the current cabin and contributes to the required amount of water.

Wesley can push each lever for any real number of seconds, but for some reason, he hates pressing levers. He wants to know how many total seconds he will have to press levers in order to fulfill the requirements for each cabin, and has enslaved politely asked you to help him.

Constraints

~1 \le N \le 10^5~

~0.001 \le R_i, X_i \le 10^9~

~0.001 \le F_i \le 0.9~

~R_i~, ~X_i~, and ~F_i~ are given with at most ~3~ decimal digits.

For any given cabin, the flow rates of adjacent pipes that lead away from cabin ~1~ will have a sum that is less than ~1~.

Subtask 1 [20%]

~1 \le N \le 10~

Subtask 2 [50%]

~1 \le N \le 2 \times 10^3~

Subtask 3 [30%]

No additional constraints.

Input Specification

The first line will contain ~N~, the number of cabins.

The next ~N~ lines will each contain two real numbers, ~R_i~ and ~X_i~.

The next ~N - 1~ lines will contain ~a_i, b_i~ and ~F_i~, indicating that there is a connection between cabins ~a_i~ and ~b_i~ with flow rate ~F_i~.

Output Specification

Output the number of seconds required for Wesley to be able to meet the requirements for each cabin. Your answer will be considered correct if it has an absolute or relative error of less than ~10^{-6}~.

Sample Input

4
1 1
2.5 10
2.5 5
5.5 5
1 2 0.25
1 3 0.25
1 4 0.4

Sample Output

10.3

Explanation for Sample

The graph is shown below.

If we press the lever at cabin ~1~ for ~10~ seconds, and the lever at cabin ~4~ for ~0.3~ seconds, all cabins will have at least the required amount of water. It can be proven that ~10.3~ is minimal.