Description

The two sides of a balance do not necessarily hang only items; they can also hang another balance. You are given several balances and the connections between them. Your task is to make all balances balance with the minimal total weight of items. A balance is balanced if and only if: weight at the left end $\times$ distance from the left end to the fulcrum $=$ weight at the right end $\times$ distance from the right end to the fulcrum. Note that the input guarantees these balances form a single whole.

Input Format

The first line contains an integer $N$ ($N \le 100$), the number of balances, numbered from $1$ to $N$.

Then follow $N$ lines, each with $4$ integers $P, Q, R, B$. $P$ and $Q$ denote the lengths on the beam from the fulcrum to the left and to the right, respectively. $R$ describes what is hung on the left: if $R = 0$, an item is hung; otherwise, the left side hangs balance $R$. $B$ describes what is hung on the right: if $B = 0$, an item is hung; otherwise, the right side hangs balance $B$.

It is guaranteed that in the optimal construction, for every balance, the sum of weight × lever arm over both sides will not exceed the int range.

Output Format

Output a single integer representing the minimal total weight of items needed to make all balances balance.

4
3 2 0 4
1 3 0 0
4 4 2 1
2 2 0 0

40

Hint

[Sample Explanation]

Translated by ChatGPT 5