Мобілі широко відомі та улюблені як рухомі витвори мистецтва. Японський комітет 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