最軽量のモビール

問題

モビールは動く芸術品として広く親しまれている.IOI 日本委員会では,JOI を広報するためにモビールを作成することになった.JOI 広報用モビールは,棒,紐(ひも),錘(おもり)の 3 種類の要素を用いて,次のように構成される.

• 棒の一方の端は青に,もう一方の端は赤に塗られている.
• 棒は両端以外の 1 箇所を支点として紐でつるされる.
• 支点から赤の端までの長さも支点から青の端までの長さも正整数である.
• 棒の両端には,紐で錘か他の棒をつるす.
• 錘は紐を用いてどれかの棒の一端につるされる.
• 錘には何もつるさない.
• 錘の重さは正整数である.
• 紐のうち 1 本だけは,片方の端をある棒をつるすためにその棒の支点に結ばれ, もう一方の端は他のどの構成要素とも結ばれていない.他の紐は全て次のいず れかを満たす.
• ある棒の端とある棒の支点を結ぶ.
• ある棒の端とある錘を結ぶ.

ただし,どの棒においても,バランスが取れている必要がある.棒と紐の重さは無視できるほど軽いので,棒と紐の重さは全て 0 であるとみなして解答せよ.つまり,それぞれの棒について,

(その棒の赤の端より下につるされている錘の重さの総計) × (その棒の支点から赤の端までの長さ) = (その棒の青の端より下につるされている錘の重さの総計) × (その棒の支点から青の端までの長さ)

であるとき,その棒はバランスが取れているとせよ.

どのような長さの棒をどのように結びモビールを構成するかは既に決まっているのだが,錘の重さがまだ決まっていない.モビールは軽い方がつりやすいため, なるべく軽いモビールを作りたい.前述したようにどの棒もバランスを取りながら, モビールの総重量を最小にするような錘の付け方を求め, そのときのモビールの総重量を出力するプログラムを作れ. プログラムには以下のモビールの構成に関する情報が与えられる.

• 棒の本数 n
• 各棒ごとの情報(棒の番号は 1 から n)
• 支点から赤の端までの長さと支点から青の端までの長さの比
• 赤の端につるす棒の番号 (錘をつるす場合は 0)
• 青の端につるす棒の番号 (錘をつるす場合は 0)

入力

入力は複数のデータセットからなる．各データセットは以下の形式で与えられる．入力はゼロ１つを含む行で終了する．

1 行目にはモビールに使われている棒の本数 n が書かれている.続く n 行 (1 ≤ n ≤ 100) には,各々の棒のデータが書かれている.i + 1 行目 (1 ≤ i ≤ n) には,4 つの整数 p, q, r, b が空白を区切りとして書かれており,棒 i において,支点から赤の端までの長さと支点から青の端までの比が p : q であり,赤の端につるされる棒の番号が r であり,青の端につるされる棒の番号が b であることを表している.ただし,棒番号 0 は錘がつるされることを表している.また,どの入力においても,モビールの重量の最小値を w とし,入力中で比を表すのに用いられる正整数の最大値を L とすると,wL < 2³¹ を満たす.

データセットの数は 15 を超えない．

出力

データセットごとにモビールの重量を１行に出力する．

入出力例

入力例

1
6 9 0 0
4
3 2 0 4
1 3 0 0
4 4 2 1
2 2 0 0
0

出力例

5
40

---