Les mobiles sont largement appréciés en tant qu'œuvres d'art cinétique. Le Comité japonais de l'IOI a décidé de créer un mobile afin de promouvoir la JOI. Le mobile promotionnel de la JOI est construit de la manière suivante à l'aide de $3$ types d'éléments : des tiges, des fils et des poids.

• L'une des extrémités de chaque tige est peinte en bleu, et l'autre extrémité est peinte en rouge.
• Chaque tige est suspendue par un fil en $1$ point autre que ses deux extrémités, qui sert de point d'appui.
• La longueur du point d'appui à l'extrémité rouge ainsi que la longueur du point d'appui à l'extrémité bleue sont des entiers strictement positifs.
• Aux deux extrémités d'une tige, on suspend par un fil soit un poids, soit une autre tige.
• Chaque poids est suspendu par un fil à l'une des extrémités d'une tige.
• Rien n'est suspendu à un poids.
• La masse de chaque poids est un entier strictement positif.
• Exactement $1$ des fils a l'une de ses extrémités attachée au point d'appui d'une tige afin de suspendre cette tige, et son autre extrémité n'est attachée à aucun autre élément constitutif. Tous les autres fils vérifient l'une des conditions suivantes :
  • Il relie l'extrémité d'une tige au point d'appui d'une tige.
  • Il relie l'extrémité d'une tige à un poids.

Toutefois, chaque tige doit être en équilibre. Comme la masse des tiges et des fils est suffisamment faible pour être négligeable, répondez en considérant que les masses de toutes les tiges et de tous les fils valent $0$. Autrement dit, pour chaque tige, on considère qu'elle est en équilibre lorsque :

(somme des masses des poids suspendus sous l'extrémité rouge de cette tige) $\times$ (longueur du point d'appui de cette tige à son extrémité rouge) $=$ (somme des masses des poids suspendus sous l'extrémité bleue de cette tige) $\times$ (longueur du point d'appui de cette tige à son extrémité bleue)

Légende des 4 schémas ci-dessus — En haut à gauche : Exemple de mobile simple ; En haut à droite : Exemple qui n'est pas un mobile car il n'est pas équilibré ; En bas à gauche : Exemple de mobile ; En bas à droite : Exemple qui n'est pas un mobile.

La façon dont les tiges de différentes longueurs sont reliées pour former le mobile est déjà fixée, mais la masse des différents poids n'est pas encore décidée. Comme un mobile plus léger est plus facile à suspendre, on souhaite fabriquer un mobile aussi léger que possible. Comme décrit précédemment, écrivez un programme qui détermine comment choisir les poids de façon à minimiser la masse totale du mobile tout en maintenant chaque tige en équilibre, et qui affiche alors la masse totale du mobile. Le programme reçoit les informations suivantes concernant la structure du mobile :

• Le nombre de tiges $n$
• Les informations pour chaque tige (les tiges sont numérotées de $1$ à $n$) :
  • Le rapport entre la longueur du point d'appui à l'extrémité rouge et la longueur du point d'appui à l'extrémité bleue
  • Le numéro de la tige suspendue à l'extrémité rouge ($0$ si un poids y est suspendu)
  • Le numéro de la tige suspendue à l'extrémité bleue ($0$ si un poids y est suspendu)

Légende des 2 schémas ci-dessus — À gauche (tige numéro $1$) : Le mobile le plus léger pour cette structure ; À droite (tige numéro $1$) : Un mobile qui n'est pas le plus léger.

Entrée

La $1$-re ligne contient le nombre de tiges $n$ utilisées dans le mobile. Les $n$ lignes suivantes ($1 \le n \le 100$) contiennent les données de chacune des tiges. La ligne $i + 1$ ($1 \le i \le n$) contient $4$ entiers $p, q, r, b$ séparés par des espaces, indiquant que pour la tige $i$, le rapport entre la longueur du point d'appui à l'extrémité rouge et la longueur du point d'appui à l'extrémité bleue est $p : q$, le numéro de la tige suspendue à l'extrémité rouge est $r$, et le numéro de la tige suspendue à l'extrémité bleue est $b$. Ici, le numéro de tige $0$ indique qu'un poids est suspendu. De plus, pour toute entrée, si $w$ désigne la valeur minimale de la masse du mobile et $L$ la valeur maximale des entiers strictement positifs utilisés dans l'entrée pour représenter les rapports, alors $w L < 2^{31}$ est vérifié.

Sortie

La sortie consiste en $1$ seule ligne affichant la masse du mobile.

Exemples d'entrée et de sortie

Exemple d'entrée 1

1
6 9 0 0

Exemple de sortie 1

5

Exemple d'entrée 2

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

Exemple de sortie 2

40