Мобили широко известны и любимы как движущиеся произведения искусства. Японский комитет 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