Uroer (mobiler) er svært populære som bevegelige kunstverk. Den japanske IOI-komiteen har bestemt seg for å lage en uro for å promotere JOI. JOI-uroen er bygget opp på følgende måte ved hjelp av $3$ typer elementer: stenger, snorer og lodd.

• Den ene enden av hver stang er malt blå, og den andre enden er malt rød.
• Hver stang henges opp i en snor i $1$ punkt utenom de to endene, som fungerer som vippepunkt.
• Både lengden fra vippepunktet til den røde enden og lengden fra vippepunktet til den blå enden er positive heltall.
• I begge endene av en stang henges det i en snor enten et lodd eller en annen stang.
• Hvert lodd henges opp ved hjelp av en snor i den ene enden av en eller annen stang.
• Ingenting henges under et lodd.
• Vekten til hvert lodd er et positivt heltall.
• Nøyaktig $1$ av snorene har den ene enden knyttet til vippepunktet på en stang for å henge opp denne stangen, mens den andre enden ikke er knyttet til noe annet element. Alle andre snorer oppfyller ett av følgende krav:
  • Den forbinder enden av en stang med vippepunktet på en stang.
  • Den forbinder enden av en stang med et lodd.

Imidlertid må hver eneste stang være i balanse. Siden vekten av stengene og snorene er så liten at den kan neglisjeres, skal du løse oppgaven ved å anta at vekten av alle stenger og snorer er $0$. Med andre ord regnes hver stang for å være i balanse når:

(summen av vektene til loddene som henger under den røde enden av stangen) $\times$ (lengden fra stangens vippepunkt til den røde enden) $=$ (summen av vektene til loddene som henger under den blå enden av stangen) $\times$ (lengden fra stangens vippepunkt til den blå enden)

Forklaring til de 4 figurene ovenfor — Øverst til venstre: Eksempel på en enkel uro; Øverst til høyre: Eksempel som ikke er en uro fordi den ikke er i balanse; Nederst til venstre: Eksempel på en uro; Nederst til høyre: Eksempel som ikke er en uro.

Hvilke lengder stengene har og hvordan de knyttes sammen for å utgjøre uroen er allerede bestemt, men vekten på loddene er ennå ikke bestemt. Siden en lettere uro er enklere å henge opp, ønsker vi å lage en så lett uro som mulig. Som beskrevet ovenfor, skriv et program som finner hvordan loddene skal velges for å minimere uroens totalvekt samtidig som hver stang holdes i balanse, og som skriver ut uroens totalvekt i dette tilfellet. Programmet får oppgitt følgende informasjon om uroens oppbygning:

• Antallet stenger $n$
• Informasjon om hver enkelt stang (stengene har nummer fra $1$ til $n$):
  • Forholdet mellom lengden fra vippepunktet til den røde enden og lengden fra vippepunktet til den blå enden
  • Nummeret på stangen som henger i den røde enden ($0$ hvis det henger et lodd der)
  • Nummeret på stangen som henger i den blå enden ($0$ hvis det henger et lodd der)

Forklaring til de 2 figurene ovenfor — Til venstre (stang nummer $1$): Den letteste uroen med denne oppbygningen; Til høyre (stang nummer $1$): En uro som ikke er den letteste.

Inndata

På den $1$. linjen står antallet stenger $n$ som brukes i uroen. På de neste $n$ linjene ($1 \le n \le 100$) står dataene for hver enkelt stang. På linje $i + 1$ ($1 \le i \le n$) står det $4$ heltall $p, q, r, b$ atskilt med mellomrom, som angir at for stang $i$ er forholdet mellom lengden fra vippepunktet til den røde enden og lengden fra vippepunktet til den blå enden lik $p : q$, nummeret på stangen som henger i den røde enden er $r$, og nummeret på stangen som henger i den blå enden er $b$. Her betyr stangnummer $0$ at det henger et lodd der. Videre gjelder det i alle inndata at dersom $w$ er minimumsverdien for uroens vekt og $L$ er maksimumsverdien blant de positive heltallene som brukes i inndataene for å angi forholdene, så er $w L < 2^{31}$ oppfylt.

Utdata

Utdataene består av kun $1$ linje, som skriver ut vekten av uroen.

Eksempler på inndata og utdata

Eksempelinndata 1

1
6 9 0 0

Eksempelutdata 1

5

Eksempelinndata 2

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

Eksempelutdata 2

40