Wesley recently bought a resort comprised of cabins, numbered from to . He needs to distribute water to his cabins, with different requirements per cabin. Wesley doesn't care if any cabin gets more than the required amount of water, as long as they get at least units.
At each cabin there is a lever, each of which produce a different output rate , meaning that units of water flow into cabin if the lever is held for one second.
The cabins are connected by a network of pipes. Wesley resides in cabin , 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 . When units of water flows into a node, each connected pipe that leads away from the head cabin transfers 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.
, , and are given with at most decimal digits.
For any given cabin, the flow rates of adjacent pipes that lead away from cabin will have a sum that is less than .
Subtask 1 [20%]
Subtask 2 [50%]
Subtask 3 [30%]
No additional constraints.
The first line will contain , the number of cabins.
The next lines will each contain two real numbers, and .
The next lines will contain and , indicating that there is a connection between cabins and with flow rate .
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 .
1 2 0.25
1 3 0.25
1 4 0.4
Explanation for Sample
The graph is shown below.
If we press the lever at cabin for seconds, and the lever at cabin for seconds, all cabins will have at least the required amount of water. It can be proven that is minimal.