تحظى المجسمات المعلقة المتحركة (Mobiles) بشعبية واسعة كقطع فنية حركية. قررت اللجنة اليابانية لأولمبياد المعلوماتية الدولي (IOI) صنع مجسم معلق للترويج لأولمبياد المعلوماتية الياباني (JOI). يتكون المجسم الترويجي لـ JOI على النحو التالي باستخدام $3$ أنواع من العناصر: القضبان، والخيوط، والأثقال.

• يُطلى أحد طرفي كل قضيب باللون الأزرق، ويُطلى الطرف الآخر باللون الأحمر.
• يُعلَّق كل قضيب بواسطة خيط من نقطة $1$ غير طرفيه تعمل كنقطة ارتكاز.
• كل من المسافة من نقطة الارتكاز إلى الطرف الأحمر والمسافة من نقطة الارتكاز إلى الطرف الأزرق عدد صحيح موجب.
• يُعلَّق في كل من طرفي القضيب بواسطة خيط إما ثقل وإما قضيب آخر.
• يُعلَّق كل ثقل بواسطة خيط في أحد طرفي قضيب ما.
• لا يُعلَّق أي شيء أسفل الثقل.
• وزن كل ثقل هو عدد صحيح موجب.
• يوجد خيط $1$ فقط مربوط من أحد طرفيه بنقطة ارتكاز قضيب ما من أجل تعليق ذلك القضيب، بينما طرفه الآخر غير مربوط بأي عنصر آخر من عناصر المجسم. أما جميع الخيوط الأخرى فيحقق كل منها أحد الشرطين التاليين:
  • يصل بين طرف قضيب ما ونقطة ارتكاز قضيب ما.
  • يصل بين طرف قضيب ما وثقل ما.

ومع ذلك، يجب أن يكون كل قضيب في حالة اتزان. وبما أن أوزان القضبان والخيوط خفيفة لدرجة يمكن إهمالها، أجب عن المسألة بافتراض أن أوزان جميع القضبان والخيوط تساوي $0$. بعبارة أخرى، لكل قضيب، يُعتبَر القضيب متزناً عندما يتحقق:

(مجموع أوزان الأثقال المعلقة أسفل الطرف الأحمر لذلك القضيب) $\times$ (الطول من نقطة ارتكاز ذلك القضيب إلى الطرف الأحمر) $=$ (مجموع أوزان الأثقال المعلقة أسفل الطرف الأزرق لذلك القضيب) $\times$ (الطول من نقطة ارتكاز ذلك القضيب إلى الطرف الأزرق)

شرح الأشكال الأربعة أعلاه — أعلى اليسار: مثال لمجسم معلق بسيط؛ أعلى اليمين: مثال ليس مجسماً معلقاً لأنه غير متزن؛ أسفل اليسار: مثال لمجسم معلق؛ أسفل اليمين: مثال ليس مجسماً معلقاً.

لقد تَقرَّر بالفعل كيف سيتم ربط القضبان وما أطوالها لتكوين المجسم المعلق، ولكن لم تتقرر بعد أوزان الأثقال. وبما أن المجسم الأخف وزناً يكون تعليقه أسهل، فإننا نرغب في صنع مجسم معلق خفيف قدر الإمكان. كما وُضِّح أعلاه، اكتب برنامجاً يجد كيفية اختيار أوزان الأثقال بحيث يصبح الوزن الكلي للمجسم المعلق أصغر ما يمكن مع الحفاظ على اتزان كل قضيب، ثم يطبع الوزن الكلي للمجسم المعلق في تلك الحالة. يُعطى للبرنامج المعلومات التالية حول بنية المجسم المعلق:

• عدد القضبان $n$
• معلومات عن كل قضيب (أرقام القضبان من $1$ إلى $n$):
  • النسبة بين الطول من نقطة الارتكاز إلى الطرف الأحمر والطول من نقطة الارتكاز إلى الطرف الأزرق
  • رقم القضيب المعلق في الطرف الأحمر ($0$ إذا كان المعلق ثقلاً)
  • رقم القضيب المعلق في الطرف الأزرق ($0$ إذا كان المعلق ثقلاً)

شرح الشكلين أعلاه — اليسار (القضيب رقم $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