Mobiles erfreuen sich als bewegliche Kunstwerke großer Beliebtheit. Das japanische IOI-Komitee hat beschlossen, ein Mobile zur Bekanntmachung der JOI zu basteln. Das JOI-Werbemobile wird unter Verwendung von $3$ Arten von Elementen – Stäben, Schnüren und Gewichten – wie folgt aufgebaut:

• Das eine Ende jedes Stabes ist blau, das andere Ende rot bemalt.
• Jeder Stab wird an $1$ Punkt außerhalb seiner beiden Enden als Drehpunkt (Aufhängepunkt) an einer Schnur aufgehängt.
• Sowohl die Länge vom Drehpunkt bis zum roten Ende als auch die Länge vom Drehpunkt bis zum blauen Ende sind positive ganze Zahlen.
• An den beiden Enden eines Stabes wird mit einer Schnur jeweils entweder ein Gewicht oder ein weiterer Stab aufgehängt.
• Jedes Gewicht wird mit einer Schnur an einem Ende irgendeines Stabes aufgehängt.
• An einem Gewicht wird nichts aufgehängt.
• Das Gewicht jedes Gewichts ist eine positive ganze Zahl.
• Genau $1$ der Schnüre ist mit einem Ende am Drehpunkt eines Stabes befestigt, um diesen Stab aufzuhängen, während ihr anderes Ende mit keinem anderen Bauelement verbunden ist. Alle anderen Schnüre erfüllen jeweils eine der folgenden Bedingungen:
  • Sie verbindet das Ende eines Stabes mit dem Drehpunkt eines Stabes.
  • Sie verbindet das Ende eines Stabes mit einem Gewicht.

Allerdings muss sich jeder Stab im Gleichgewicht befinden. Da das Gewicht der Stäbe und Schnüre vernachlässigbar klein ist, löse die Aufgabe unter der Annahme, dass das Gewicht aller Stäbe und Schnüre $0$ beträgt. Das heißt, für jeden Stab gilt er als im Gleichgewicht befindlich, wenn:

(Gesamtgewicht der unterhalb des roten Endes dieses Stabes aufgehängten Gewichte) $\times$ (Länge vom Drehpunkt dieses Stabes bis zum roten Ende) $=$ (Gesamtgewicht der unterhalb des blauen Endes dieses Stabes aufgehängten Gewichte) $\times$ (Länge vom Drehpunkt dieses Stabes bis zum blauen Ende)

Bildunterschrift zu den 4 obigen Abbildungen — Oben links: Beispiel für ein einfaches Mobile; Oben rechts: Beispiel, das kein Mobile ist, da es nicht im Gleichgewicht ist; Unten links: Beispiel für ein Mobile; Unten rechts: Beispiel, das kein Mobile ist.

Wie Stäbe welcher Längen miteinander verbunden werden, um das Mobile zu bilden, steht bereits fest, doch die Gewichte der einzelnen Gewichte sind noch nicht festgelegt. Da sich ein leichteres Mobile einfacher aufhängen lässt, möchten wir ein möglichst leichtes Mobile bauen. Schreibe ein Programm, das – wie oben beschrieben – unter Wahrung des Gleichgewichts an jedem Stab eine Wahl der Gewichte bestimmt, die das Gesamtgewicht des Mobiles minimiert, und das damalige Gesamtgewicht des Mobiles ausgibt. Dem Programm werden folgende Informationen über den Aufbau des Mobiles gegeben:

• Die Anzahl der Stäbe $n$
• Informationen zu jedem einzelnen Stab (die Stäbe sind von $1$ bis $n$ nummeriert):
  • Das Verhältnis der Länge vom Drehpunkt zum roten Ende zur Länge vom Drehpunkt zum blauen Ende
  • Die Nummer des am roten Ende aufgehängten Stabes ($0$, falls dort ein Gewicht aufgehängt wird)
  • Die Nummer des am blauen Ende aufgehängten Stabes ($0$, falls dort ein Gewicht aufgehängt wird)

Bildunterschrift zu den 2 obigen Abbildungen — Links (Stab Nummer $1$): Das leichteste Mobile bei diesem Aufbau; Rechts (Stab Nummer $1$): Ein Mobile, das nicht das leichteste ist.

Eingabe

In der $1$. Zeile steht die Anzahl $n$ der im Mobile verwendeten Stäbe. In den folgenden $n$ Zeilen ($1 \le n \le 100$) stehen die Daten der einzelnen Stäbe. In der Zeile $i + 1$ ($1 \le i \le n$) stehen durch Leerzeichen getrennt $4$ ganze Zahlen $p, q, r, b$; sie geben an, dass bei Stab $i$ das Verhältnis der Länge vom Drehpunkt bis zum roten Ende zur Länge vom Drehpunkt bis zum blauen Ende gleich $p : q$ ist, die Nummer des am roten Ende aufgehängten Stabes $r$ ist und die Nummer des am blauen Ende aufgehängten Stabes $b$ ist. Dabei bedeutet die Stabnummer $0$, dass dort ein Gewicht aufgehängt ist. Ferner gilt für jede Eingabe: Wenn $w$ den minimalen Wert des Gewichts des Mobiles und $L$ den maximalen Wert der in der Eingabe zur Darstellung der Verhältnisse verwendeten positiven ganzen Zahlen bezeichnet, so ist $w L < 2^{31}$ erfüllt.

Ausgabe

Die Ausgabe besteht aus nur $1$ Zeile, in der das Gewicht des Mobiles ausgegeben wird.

Beispiele für Ein- und Ausgabe

Beispieleingabe 1

1
6 9 0 0

Beispielausgabe 1

5

Beispieleingabe 2

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

Beispielausgabe 2

40