吊饰（Mobile，平衡悬挂饰品）作为一种动态艺术品广受人们喜爱。IOI 日本委员会决定制作一个吊饰来宣传 JOI。JOI 宣传用吊饰使用杆、绳、秤砣这 $3$ 种要素，按如下方式构成：

• 杆的一端涂成蓝色，另一端涂成红色。
• 杆以除两端以外的 $1$ 处作为支点，用绳子悬挂起来。
• 从支点到红端的长度以及从支点到蓝端的长度均为正整数。
• 杆的两端分别用绳子悬挂着秤砣或其他杆。
• 秤砣用绳子悬挂在某根杆的一端。
• 秤砣下面不悬挂任何东西。
• 秤砣的重量为正整数。
• 在所有绳子中，只有 $1$ 根绳子的一端为了悬挂某根杆而绑在该杆的支点上，且另一端不与任何其他构成要素相连。其余所有绳子均满足以下条件之一：
  • 连接某根杆的一端与某根杆的支点。
  • 连接某根杆的一端与某个秤砣。

但是，每一根杆都必须保持平衡。由于杆和绳子的重量轻到可以忽略不计，请将杆和绳子的重量全部视为 $0$ 来作答。也就是说，对于每一根杆，当满足：

（悬挂在该杆红端下方的秤砣的总重量）$\times$（从该杆的支点到红端的长度）$=$（悬挂在该杆蓝端下方的秤砣的总重量）$\times$（从该杆的支点到蓝端的长度）

上方四幅图说明——左上：简单吊饰的例子；右上：未保持平衡因而不是吊饰的例子；左下：吊饰的例子；右下：不是吊饰的例子。

虽然用什么长度的杆以及如何连接来构成吊饰已经确定，但各个秤砣的重量尚未确定。由于吊饰越轻越容易悬挂，我们希望制作出尽可能轻的吊饰。请编写一个程序，如前所述在使每一根杆都保持平衡的前提下，求出使吊饰总重量最小的秤砣挂法，并输出此时吊饰的总重量。程序将获得如下关于吊饰构成的信息：

• 杆的根数 $n$
• 每根杆的信息（杆的编号为 $1$ 到 $n$）：
  • 从支点到红端的长度与从支点到蓝端的长度之比
  • 红端所悬挂的杆的编号（若悬挂秤砣则为 $0$）
  • 蓝端所悬挂的杆的编号（若悬挂秤砣则为 $0$）

上方两幅图说明——左（杆编号 $1$）：此结构下最轻的吊饰；右（杆编号 $1$）：非最轻的吊饰。

输入

第 $1$ 行写有吊饰所使用的杆的根数 $n$。接下来的 $n$ 行（$1 \le n \le 100$）写有各根杆的数据。第 $i + 1$ 行（$1 \le i \le n$）写有以空格分隔的 $4$ 个整数 $p, q, r, b$，表示对于杆 $i$，从支点到红端的长度与从支点到蓝端的长度之比为 $p : q$，悬挂在红端的杆编号为 $r$，悬挂在蓝端的杆编号为 $b$。其中，杆编号 $0$ 表示悬挂的是秤砣。此外，在所有输入中，设吊饰重量的最小值为 $w$，输入中用于表示比例的正整数的最大值为 $L$，则均满足 $w L < 2^{31}$。

输出

输出仅 $1$ 行，输出吊饰的重量。

样例输入与输出

样例输入 1

1
6 9 0 0

样例输出 1

5

样例输入 2

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

样例输出 2

40