Hengiskraut (mobile) nýtur mikilla vinsælda sem hreyfanlegt listaverk. Japanska IOI-nefndin ákvað að búa til hengiskraut til að kynna JOI. Kynningarhengiskraut JOI er sett saman á eftirfarandi hátt úr $3$ tegundum eininga: stöngum, böndum og lóðum.

• Annar endi hverrar stangar er málaður blár en hinn endinn er málaður rauður.
• Hver stöng er hengd upp í band á $1$ punkti öðrum en endum hennar tveimur, sem virkar sem veltipunktur.
• Bæði lengdin frá veltipunktinum að rauða endanum og lengdin frá veltipunktinum að bláa endanum eru jákvæðar heiltölur.
• Á báðum endum stangar er annaðhvort lóð eða önnur stöng hengd upp með bandi.
• Hvert lóð er hengt upp með bandi í annan enda einhverrar stangar.
• Ekkert er hengt neðan í lóð.
• Þyngd hvers lóðs er jákvæð heiltala.
• Nákvæmlega $1$ bandanna er þannig að annar endi þess er bundinn við veltipunkt einhverrar stangar til að hengja þá stöng upp, en hinn endi þess er ekki bundinn við neina aðra einingu. Öll önnur bönd uppfylla annaðhvort af eftirfarandi skilyrðum:
  • Það tengir enda einhverrar stangar við veltipunkt einhverrar stangar.
  • Það tengir enda einhverrar stangar við eitthvert lóð.

Hins vegar verður hver stöng að vera í jafnvægi. Þar sem þyngd stanganna og bandanna er svo lítil að hún er hverfandi skal leysa verkefnið út frá þeirri forsendu að þyngd allra stanga og banda sé $0$. Með öðrum orðum telst hver stöng vera í jafnvægi þegar:

(heildarþyngd lóða sem hanga fyrir neðan rauða enda stangarinnar) $\times$ (lengdin frá veltipunkti stangarinnar að rauða endanum) $=$ (heildarþyngd lóða sem hanga fyrir neðan bláa enda stangarinnar) $\times$ (lengdin frá veltipunkti stangarinnar að bláa endanum)

Skýring við 4 myndirnar hér að ofan — Efst til vinstri: Dæmi um einfalt hengiskraut; Efst til hægri: Dæmi sem er ekki hengiskraut vegna þess að það er ekki í jafnvægi; Neðst til vinstri: Dæmi um hengiskraut; Neðst til hægri: Dæmi sem er ekki hengiskraut.

Þegar hefur verið ákveðið hvernig stangir af hvaða lengdum eru tengdar saman til að mynda hengiskrautið, en þyngdir lóðanna hafa enn ekki verið ákveðnar. Þar sem auðveldara er að hengja upp léttara hengiskraut viljum við búa til eins létt hengiskraut og mögulegt er. Eins og lýst er hér að ofan skaltu skrifa forrit sem finnur hvernig hengja á lóðin þannig að heildarþyngd hengiskrautsins verði sem minnst á meðan hver stöng helst í jafnvægi, og prentar út heildarþyngd hengiskrautsins í því tilviki. Forritinu eru gefnar eftirfarandi upplýsingar um uppbyggingu hengiskrautsins:

• Fjöldi stanga $n$
• Upplýsingar fyrir hverja stöng (númer stanganna eru frá $1$ til $n$):
  • Hlutfall lengdarinnar frá veltipunktinum að rauða endanum og lengdarinnar frá veltipunktinum að bláa endanum
  • Númer stangarinnar sem hengd er í rauða endann ($0$ ef lóð er hengt þar)
  • Númer stangarinnar sem hengd er í bláa endann ($0$ ef lóð er hengt þar)

Skýring við 2 myndirnar hér að ofan — Til vinstri (stöng númer $1$): Léttasta hengiskrautið með þessari uppbyggingu; Til hægri (stöng númer $1$): Hengiskraut sem er ekki það léttasta.

Inntak

Í $1$. línu er fjöldi stanga $n$ sem notaðar eru í hengiskrautinu. Í næstu $n$ línum ($1 \le n \le 100$) eru gögn fyrir hverja stöng. Í línu $i + 1$ ($1 \le i \le n$) eru $4$ heiltölur $p, q, r, b$ aðskildar með bilum, sem gefa til kynna að fyrir stöng $i$ sé hlutfall lengdarinnar frá veltipunktinum að rauða endanum og lengdarinnar frá veltipunktinum að bláa endanum $p : q$, númer stangarinnar sem hengd er í rauða endann sé $r$ og númer stangarinnar sem hengd er í bláa endann sé $b$. Hér táknar stangarnúmerið $0$ að lóð sé hengt þar. Að auki gildir í öllum inntaksgögnum að ef $w$ er lágmarksgildi þyngdar hengiskrautsins og $L$ er hámarksgildi jákvæðu heiltalnanna sem notaðar eru í inntakinu til að tákna hlutföllin, þá er $w L < 2^{31}$ uppfyllt.

Úttak

Úttakið samanstendur af $1$ línu sem prentar út þyngd hengiskrautsins.

Dæmi um inntak og úttak

Dæmi um inntak 1

1
6 9 0 0

Dæmi um úttak 1

5

Dæmi um inntak 2

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

Dæmi um úttak 2

40