Minimal Weight Balancing of Nested Scales

You are given a system of interconnected scales. Unlike ordinary scales that have weights hung on both sides, here each endpoint of a scale can either have a simple weight (an item) or another scale hanging from it. A scale is in equilibrium if and only if the following condition is met:

\(\text{(weight at left)} \times \text{(left distance)} = \text{(weight at right)} \times \text{(right distance)}\)

Each weight (item) can be chosen arbitrarily, but your task is to assign positive integer weights to all items so that every scale is in balance and the total weight of all items (the sum of all leaf weights) is minimized.

The input describes n scales. Each scale is described by its left arm length, right arm length and what hangs on each end. An endpoint can be either 0, representing a free-hanging item, or 1 representing another scale. If an endpoint has a scale hanging from it, the corresponding scale id is provided. The scales form a single connected structure (i.e. there is exactly one scale that is not hung from any other scale – the top scale).

For example, consider a simple scale with two items. If the left distance is \(L\) and the right distance is \(R\), the equilibrium condition is:

[ \text{left weight} \times L = \text{right weight} \times R. ]

The minimal integer solution for the two items is:

[ \text{left weight} = \frac{R}{\gcd(L,R)}, \quad \text{right weight} = \frac{L}{\gcd(L,R)}. ]

</p>

In the case of nested scales, the total weight hanging on an endpoint is the minimal balanced weight of the whole subtree. Your task is to compute the overall minimal total weight of items required to balance the entire structure.

inputFormat

The first line contains a single integer n (n ≥ 1), the number of scales.

Then follow n lines. The i-th line (1-indexed) describes scale i with 6 integers:

• L R: the distances from the left endpoint and the right endpoint to the support.
• lt lchild: if lt is 0 then an item hangs on the left pan, if lt is 1 then a scale with id lchild hangs on the left pan.
• rt rchild: similarly, if rt is 0 then an item hangs on the right pan, if rt is 1 then a scale with id rchild hangs on the right pan.

The structure is connected; that is, there is exactly one scale that is not hung on any other scale – the top scale.

Note: For endpoints that are items (lt or rt equal to 0), the subsequent number (lchild or rchild) is a dummy value (normally 0) and should be ignored.

outputFormat

Output a single integer – the minimal total weight of items required to balance the entire structure.

sample

1
3 4 0 0 0 0

7

</p>