Mobiler är vida omtyckta som rörliga konstverk. Japanska IOI-kommittén har beslutat att tillverka en mobil för att göra reklam för JOI. JOI-reklammobilen byggs upp på följande sätt med hjälp av $3$ sorters element: pinnar, snören och vikter.

• Den ena änden av varje pinne är målad blå, och den andra änden är målad röd.
• Varje pinne hängs upp i ett snöre i $1$ punkt skild från dess båda ändar som fungerar som vridningspunkt.
• Såväl längden från vridningspunkten till den röda änden som längden från vridningspunkten till den blå änden är positiva heltal.
• I båda ändarna av en pinne hänger man med ett snöre antingen en vikt eller en annan pinne.
• Varje vikt hängs med ett snöre i ena änden av någon pinne.
• Ingenting hängs i en vikt.
• Vikten hos varje vikt är ett positivt heltal.
• Exakt $1$ av snörena har sin ena ände knuten till vridningspunkten på någon pinne för att hänga upp den pinnen, medan dess andra ände inte är knuten till något annat ingående element. Alla andra snören uppfyller ett av följande villkor:
  • Det förbinder änden på någon pinne med vridningspunkten på någon pinne.
  • Det förbinder änden på någon pinne med någon vikt.

Varje pinne måste dock vara i jämvikt. Eftersom pinnarnas och snörenas vikt är så liten att den kan försummas ska du lösa uppgiften under antagandet att alla pinnar och snören har vikten $0$. Med andra ord betraktas varje pinne som varande i jämvikt när:

(totala vikten av de vikter som hänger nedanför pinnens röda ände) $\times$ (längden från pinnens vridningspunkt till den röda änden) $=$ (totala vikten av de vikter som hänger nedanför pinnens blå ände) $\times$ (längden från pinnens vridningspunkt till den blå änden)

Beskrivning av de 4 figurerna ovan — Uppe till vänster: Exempel på en enkel mobil; Uppe till höger: Exempel som inte är en mobil eftersom den inte är i jämvikt; Nere till vänster: Exempel på en mobil; Nere till höger: Exempel som inte är en mobil.

Hur pinnar av vilka längder ska knytas ihop för att bilda mobilen är redan bestämt, men vikternas vikter är ännu inte bestämda. Eftersom en lättare mobil är enklare att hänga upp vill vi göra en så lätt mobil som möjligt. Skriv ett program som, på det sätt som beskrivits ovan, bestämmer hur vikterna ska fästas för att minimera mobilens totalvikt samtidigt som varje pinne hålls i jämvikt, och som skriver ut mobilens totalvikt i detta fall. Programmet får följande information om mobilens uppbyggnad:

• Antalet pinnar $n$
• Information för varje pinne (pinnarna är numrerade från $1$ till $n$):
  • Förhållandet mellan längden från vridningspunkten till den röda änden och längden från vridningspunkten till den blå änden
  • Numret på den pinne som hänger i den röda änden ($0$ om en vikt hänger där)
  • Numret på den pinne som hänger i den blå änden ($0$ om en vikt hänger där)

Beskrivning av de 2 figurerna ovan — Till vänster (pinne nummer $1$): Den lättaste mobilen med denna uppbyggnad; Till höger (pinne nummer $1$): En mobil som inte är den lättaste.

Indata

På den $1$:a raden står antalet pinnar $n$ som används i mobilen. På de följande $n$ raderna ($1 \le n \le 100$) står data för var och en av pinnarna. På rad $i + 1$ ($1 \le i \le n$) står $4$ heltal $p, q, r, b$ åtskilda av blanksteg, vilket anger att för pinne $i$ är förhållandet mellan längden från vridningspunkten till den röda änden och längden från vridningspunkten till den blå änden lika med $p : q$, numret på pinnen som hänger i den röda änden är $r$, och numret på pinnen som hänger i den blå änden är $b$. Här anger pinnens nummer $0$ att en vikt är upphängd där. Vidare gäller för alla indata att om $w$ är det minsta värdet på mobilens vikt och $L$ är det största värdet bland de positiva heltal som används i indata för att ange förhållandena, så är $w L < 2^{31}$ uppfyllt.

Utdata

Utdata består av endast $1$ rad som skriver ut mobilens vikt.

Exempel på indata och utdata

Exempelindata 1

1
6 9 0 0

Exempelutdata 1

5

Exempelindata 2

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

Exempelutdata 2

40