Mobilet ovat laajalti suosittuja liikkuvina taideteoksina. Japanin IOI-komitea päätti valmistaa mobilen JOI:ngga tiedottamista varten. JOI:n mainosmobile rakennetaan seuraavasti käyttäen $3$ tyyppisiä osia: tankoja, naruja ja punnuksia.

• Jokaisen tangon toinen pää on maalattu siniseksi ja toinen pää punaiseksi.
• Jokainen tanko ripustetaan narulla $1$ pisteestä, joka ei ole kumpikaan sen päistä ja joka toimii tukipisteenä.
• Sekä pituus tukipisteestä punaiseen päähän että pituus tukipisteestä siniseen päähän ovat positiivisia kokonaislukuja.
• Tangon molempiin päihin ripustetaan narulla joko punnus tai toinen tanko.
• Jokainen punnus ripustetaan narulla jonkin tangon toiseen päähän.
• Punnukseen ei ripusteta mitään.
• Jokaisen punnuksen paino on positiivinen kokonaisluku.
• Tarkalleen $1$ naruista on sellainen, jonka toinen pää on sidottu jonkin tangon tukipisteeseen kyseisen tangon ripustamiseksi ja jonka toista päätä ei ole sidottu mihinkään muuhun rakenneosaan. Kaikki muut narut täyttävät jommankumman seuraavista ehdoista:
  • Se yhdistää jonkin tangon pään ja jonkin tangon tukipisteen.
  • Se yhdistää jonkin tangon pään ja jonkin punnuksen.

Jokaisen tangon täytyy kuitenkin olla tasapainossa. Koska tankojen ja narujen paino on mitättömän pieni, ratkaise tehtävä olettaen, että kaikkien tankojen ja narujen paino on $0$. Toisin sanoen jokaisen tangon katsotaan olevan tasapainossa silloin, kun:

(kyseisen tangon punaisen pään alapuolelle ripustettujen punnusten painojen summa) $\times$ (pituus kyseisen tangon tukipisteestä punaiseen päähän) $=$ (kyseisen tangon sinisen pään alapuolelle ripustettujen punnusten painojen summa) $\times$ (pituus kyseisen tangon tukipisteestä siniseen päähän)

Yllä olevien 4 kuvan selitys — Ylhäällä vasemmalla: Esimerkki yksinkertaisesta mobilesta; Ylhäällä oikealla: Esimerkki, joka ei ole mobile, koska se ei ole tasapainossa; Alhaalla vasemmalla: Esimerkki mobilesta; Alhaalla oikealla: Esimerkki, joka ei ole mobile.

Se, minkä pituisia tankoja ja miten yhdistettyinä mobileen käytetään, on jo päätetty, mutta punnusten painoja ei ole vielä päätetty. Koska kevyempi mobile on helpompi ripustaa, haluamme tehdä mahdollisimman kevyen mobilen. Laadi ohjelma, joka edellä kuvatulla tavalla etsii tavan asettaa punnukset niin, että jokainen tanko pysyy tasapainossa ja mobilen kokonaispaino on mahdollisimman pieni, ja tulostaa mobilen kokonaispainon tässä tapauksessa. Ohjelmalle annetaan seuraavat tiedot mobilen rakenteesta:

• Tankojen lukumäärä $n$
• Jokaisen tangon tiedot (tankojen numerot ovat $1$:stä $n$:ään):
  • Tukipisteestä punaiseen päähän mitatun pituuden ja tukipisteestä siniseen päähän mitatun pituuden suhde
  • Punaiseen päähän ripustettavan tangon numero ($0$, jos siihen ripustetaan punnus)
  • Siniseen päähän ripustettavan tangon numero ($0$, jos siihen ripustetaan punnus)

Yllä olevien 2 kuvan selitys — Vasemmalla (tanko numero $1$): Tämän rakenteen kevyin mobile; Oikealla (tanko numero $1$): Mobile, joka ei ole kevyin.

Syöte

Rivillä $1$ on mobilessa käytettyjen tankojen lukumäärä $n$. Seuraavilla $n$ rivillä ($1 \le n \le 100$) ovat kunkin tangon tiedot. Rivillä $i + 1$ ($1 \le i \le n$) on $4$ välilyönnein erotettua kokonaislukua $p, q, r, b$, jotka ilmoittavat, että tangossa $i$ tukipisteestä punaiseen päähän mitatun pituuden suhde tukipisteestä siniseen päähän mitattuun pituuteen on $p : q$, punaiseen päähän ripustettavan tangon numero on $r$ ja siniseen päähän ripustettavan tangon numero on $b$. Tässä tangon numero $0$ tarkoittaa, että päähän ripustetaan punnus. Lisäksi jokaisessa syötteessä pätee $w L < 2^{31}$, missä $w$ on mobilen painon pienin mahdollinen arvo ja $L$ on syötteessä suhteiden ilmoittamiseen käytettyjen positiivisten kokonaislukujen suurin arvo.

Tuloste

Tuloste koostuu vain $1$ rivistä, jolle tulostetaan mobilen paino.

Esimerkit syötteestä ja tulosteesta

Esimerkkisyöte 1

1
6 9 0 0

Esimerkkituloste 1

5

Esimerkkisyöte 2

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

Esimerkkituloste 2

40