Мобильдер қозғалмалы өнер туындысы ретінде кеңінен танымал. IOI Жапония комитеті JOI-ды насихаттау үшін мобиль жасауды ұйғарды. JOI-ды насихаттауға арналған мобиль таяқша, жіп және гір тасы сияқты $3$ түрлі элементті қолдану арқылы келесідей құрастырылады:

• Әр таяқшаның бір ұшы көк түске, ал екінші ұшы қызыл түске боялған.
• Әр таяқша екі ұшынан басқа $1$ нүктені тірек нүктесі ретінде алып, жіппен ілінеді.
• Тірек нүктесінен қызыл ұшына дейінгі ұзындық та, тірек нүктесінен көк ұшына дейінгі ұзындық та оң бүтін сан болып табылады.
• Таяқшаның екі ұшына жіппен гір тасы немесе басқа таяқша ілінеді.
• Әр гір тасы жіптің көмегімен қандай да бір таяқшаның бір ұшына ілінеді.
• Гір тасына ештеңе ілінбейді.
• Әр гір тасының салмағы оң бүтін сан болып табылады.
• Жіптердің ішінде тек $1$ жіптің ғана бір ұшы қандай да бір таяқшаны ілу үшін сол таяқшаның тірек нүктесіне байланған, ал екінші ұшы басқа ешбір құрамдас элементпен байланбаған. Қалған барлық жіптер келесі шарттардың бірін қанағаттандырады:
  • Қандай да бір таяқшаның ұшы мен қандай да бір таяқшаның тірек нүктесін жалғайды.
  • Қандай да бір таяқшаның ұшы мен қандай да бір гір тасын жалғайды.

Алайда әрбір таяқша тепе-теңдікте болуы қажет. Таяқшалар мен жіптердің салмағы еленбейтіндей жеңіл болғандықтан, барлық таяқшалар мен жіптердің салмағын $0$ деп есептеп жауап беріңіз. Яғни, әрбір таяқша үшін:

(сол таяқшаның қызыл ұшынан төмен ілінген гір тастары салмақтарының қосындысы) $\times$ (сол таяқшаның тірек нүктесінен қызыл ұшына дейінгі ұзындық) $=$ (сол таяқшаның көк ұшынан төмен ілінген гір тастары салмақтарының қосындысы) $\times$ (сол таяқшаның тірек нүктесінен көк ұшына дейінгі ұзындық)

Жоғарыдағы 4 суреттің сипаттамасы — Сол жақ жоғарыда: қарапайым мобиль мысалы; Оң жақ жоғарыда: тепе-теңдік сақталмағандықтан мобиль болып табылмайтын мысал; Сол жақ төменде: мобиль мысалы; Оң жақ төменде: мобиль болып табылмайтын мысал.

Мобильді құрастыру үшін қандай ұзындықтағы таяқшаларды қалай байлау керектігі алдын ала шешіліп қойған, бірақ гір тастарының салмағы әлі белгіленген жоқ. Мобиль неғұрлым жеңіл болса, оны ілу соғұрлым оңай болғандықтан, біз мүмкіндігінше жеңіл мобиль жасағымыз келеді. Жоғарыда айтылғандай, барлық таяқшалардың тепе-теңдігін сақтай отырып, мобильдің жалпы салмағын барынша азайтатындай гір тастарын тағу әдісін табатын және сол кездегі мобильдің жалпы салмағын шығаратын программа жазыңыз. Программаға мобильдің құрылымы туралы келесі ақпарат беріледі:

• Таяқшалар саны $n$
• Әр таяқша бойынша ақпарат (таяқшалардың нөмірлері $1$-ден $n$-ге дейін):
  • Тірек нүктесінен қызыл ұшына дейінгі ұзындық пен тірек нүктесінен көк ұшына дейінгі ұзындықтың қатынасы
  • Қызыл ұшына ілінетін таяқшаның нөмірі (егер гір тасы ілінсе $0$)
  • Көк ұшына ілінетін таяқшаның нөмірі (егер гір тасы ілінсе $0$)

Жоғарыдағы 2 суреттің сипаттамасы — Сол жақта ($1$-нөмірлі таяқша): осы құрылымдағы ең жеңіл мобиль; Оң жақта ($1$-нөмірлі таяқша): ең жеңіл емес мобиль.

Кіріс деректер

$1$-ші жолда мобильде қолданылған таяқшалар саны $n$ жазылған. Келесі $n$ жолда ($1 \le n \le 100$) әрбір таяқшаның деректері жазылған. $i + 1$-ші жолда ($1 \le i \le n$) бос орын арқылы бөлінген $4$ бүтін сан $p, q, r, b$ жазылған; бұл $i$-ші таяқшада тірек нүктесінен қызыл ұшына дейінгі ұзындық пен тірек нүктесінен көк ұшына дейінгі ұзындықтың қатынасы $p : q$ екенін, қызыл ұшына ілінетін таяқшаның нөмірі $r$ екенін және көк ұшына ілінетін таяқшаның нөмірі $b$ екенін білдіреді. Мұндағы $0$ таяқша нөмірі гір тасы ілінетінін білдіреді. Сонымен қатар кез келген кіріс деректерінде мобиль салмағының ең кіші мәнін $w$ деп, ал кіріс деректерінде қатынастарды өрнектеу үшін қолданылатын оң бүтін сандардың ең үлкен мәнін $L$ деп алсақ, $w L < 2^{31}$ шарты орындалады.

Шығыс деректер

Шығыс деректер тек $1$ жолдан тұрады — мобильдің салмағын шығарыңыз.

Кіріс және шығыс мысалдары

1-ші кіріс мысалы

1
6 9 0 0

1-ші шығыс мысалы

5

2-ші кіріс мысалы

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

2-ші шығыс мысалы

40