מוביילים אהובים מאוד כיצירות אמנות קינטית. הוועדה היפנית של ה-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