I mobile (sculture mobili sospese) sono ampiamente apprezzati come opere d'arte cinetica. Il Comitato Giapponese delle IOI ha deciso di realizzare un mobile per promuovere le JOI. Il mobile promozionale delle JOI è costruito nel modo seguente utilizzando $3$ tipi di elementi: aste, fili e pesi.

• Un'estremità di ciascuna asta è dipinta di blu e l'altra estremità è dipinta di rosso.
• Ciascuna asta è sospesa mediante un filo in $1$ punto diverso dalle sue due estremità, che funge da fulcro.
• Sia la lunghezza dal fulcro all'estremità rossa sia la lunghezza dal fulcro all'estremità blu sono interi positivi.
• Alle due estremità di un'asta è sospeso, tramite un filo, un peso oppure un'altra asta.
• Ciascun peso è sospeso tramite un filo a una delle estremità di qualche asta.
• A un peso non è sospeso nulla.
• Il peso di ciascun peso è un intero positivo.
• Esattamente $1$ dei fili ha un'estremità legata al fulcro di una qualche asta per sospendere tale asta, mentre l'altra estremità non è legata ad alcun altro elemento costitutivo. Tutti gli altri fili soddisfano una delle seguenti condizioni:
  • Collega l'estremità di una qualche asta e il fulcro di una qualche asta.
  • Collega l'estremità di una qualche asta e un qualche peso.

Tuttavia, ogni asta deve essere in equilibrio. Poiché il peso delle aste e dei fili è così leggero da essere trascurabile, risolvi il problema assumendo che il peso di tutte le aste e di tutti i fili sia $0$. In altre parole, per ciascuna asta, si considera che l'asta sia in equilibrio quando:

(somma dei pesi dei pesi sospesi al di sotto dell'estremità rossa di quell'asta) $\times$ (lunghezza dal fulcro di quell'asta all'estremità rossa) $=$ (somma dei pesi dei pesi sospesi al di sotto dell'estremità blu di quell'asta) $\times$ (lunghezza dal fulcro di quell'asta all'estremità blu)

Didascalia dei 4 diagrammi sopra — In alto a sinistra: Esempio di mobile semplice; In alto a destra: Esempio che non è un mobile perché non è in equilibrio; In basso a sinistra: Esempio di mobile; In basso a destra: Esempio che non è un mobile.

Come collegare aste di quali lunghezze per costruire il mobile è già stato deciso, ma i pesi dei singoli pesi non sono ancora stati decisi. Poiché un mobile più leggero è più facile da appendere, vogliamo realizzare un mobile il più leggero possibile. Come descritto sopra, scrivi un programma che trovi come applicare i pesi in modo da minimizzare il peso totale del mobile mantenendo ogni asta in equilibrio, e stampi il peso totale del mobile in tale caso. Al programma vengono fornite le seguenti informazioni riguardanti la struttura del mobile:

• Il numero di aste $n$
• Informazioni per ciascuna asta (i numeri delle aste vanno da $1$ a $n$):
  • Il rapporto tra la lunghezza dal fulcro all'estremità rossa e la lunghezza dal fulcro all'estremità blu
  • Il numero dell'asta sospesa all'estremità rossa ($0$ se è sospeso un peso)
  • Il numero dell'asta sospesa all'estremità blu ($0$ se è sospeso un peso)

Didascalia dei 2 diagrammi sopra — Sinistra (asta numero $1$): Il mobile più leggero con questa struttura; Destra (asta numero $1$): Un mobile che non è il più leggero.

Input

Nella $1$-a riga è scritto il numero di aste $n$ utilizzate nel mobile. Nelle successive $n$ righe ($1 \le n \le 100$) sono scritti i dati di ciascuna asta. Nella riga $i + 1$ ($1 \le i \le n$) sono scritti $4$ interi $p, q, r, b$ separati da spazi, i quali indicano che nell'asta $i$ il rapporto tra la lunghezza dal fulcro all'estremità rossa e la lunghezza dal fulcro all'estremità blu è $p : q$, il numero dell'asta sospesa all'estremità rossa è $r$ e il numero dell'asta sospesa all'estremità blu è $b$. Qui, il numero di asta $0$ indica che è sospeso un peso. Inoltre, in ogni input, detto $w$ il valore minimo del peso del mobile e $L$ il valore massimo degli interi positivi utilizzati nell'input per rappresentare i rapporti, vale sempre $w L < 2^{31}$.

Output

L'output è costituito da $1$ sola riga, che riporta il peso del mobile.

Esempi di input e output

Esempio di input 1

1
6 9 0 0

Esempio di output 1

5

Esempio di input 2

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

Esempio di output 2

40