Los móviles son ampliamente apreciados como obras de arte cinético. El Comité Japonés de la IOI decidió crear un móvil para promocionar la JOI. El móvil promocional de la JOI se construye de la siguiente manera utilizando $3$ tipos de elementos: varillas, cuerdas y pesas.

• Uno de los extremos de cada varilla está pintado de azul y el otro extremo está pintado de rojo.
• Cada varilla se suspende mediante una cuerda por $1$ punto distinto de sus dos extremos como punto de apoyo.
• Tanto la longitud desde el punto de apoyo hasta el extremo rojo como la longitud desde el punto de apoyo hasta el extremo azul son números enteros positivos.
• En ambos extremos de una varilla se suspende, mediante una cuerda, una pesa u otra varilla.
• Cada pesa se suspende mediante una cuerda de uno de los extremos de alguna varilla.
• De una pesa no se suspende nada.
• El peso de cada pesa es un número entero positivo.
• Exactamente $1$ de las cuerdas tiene uno de sus extremos atado al punto de apoyo de alguna varilla para suspender dicha varilla, y su otro extremo no está atado a ningún otro elemento constitutivo. Todas las demás cuerdas cumplen una de las siguientes condiciones:
  • Une el extremo de alguna varilla con el punto de apoyo de alguna varilla.
  • Une el extremo de alguna varilla con alguna pesa.

Sin embargo, todas las varillas deben estar equilibradas. Dado que el peso de las varillas y de las cuerdas es tan ligero que resulta despreciable, responde considerando que el peso de todas las varillas y cuerdas es $0$. Es decir, para cada varilla, se considera que la varilla está equilibrada cuando:

(suma de los pesos de las pesas suspendidas por debajo del extremo rojo de esa varilla) $\times$ (longitud desde el punto de apoyo de esa varilla hasta el extremo rojo) $=$ (suma de los pesos de las pesas suspendidas por debajo del extremo azul de esa varilla) $\times$ (longitud desde el punto de apoyo de esa varilla hasta el extremo azul)

Leyenda de los 4 diagramas de arriba — Arriba a la izquierda: Ejemplo de un móvil sencillo; Arriba a la derecha: Ejemplo que no es un móvil porque no está equilibrado; Abajo a la izquierda: Ejemplo de un móvil; Abajo a la derecha: Ejemplo que no es un móvil.

Ya está decidido qué longitudes de varillas y cómo se conectan para construir el móvil, pero aún no se ha decidido el peso de las pesas. Como un móvil más ligero es más fácil de colgar, queremos construir un móvil lo más ligero posible. Tal como se describió anteriormente, escribe un programa que determine cómo colocar las pesas para minimizar el peso total del móvil manteniendo equilibradas todas las varillas, e imprima el peso total del móvil en ese caso. Al programa se le proporciona la siguiente información sobre la estructura del móvil:

• El número de varillas $n$
• Información de cada varilla (los números de las varillas van de $1$ a $n$):
  • La razón entre la longitud desde el punto de apoyo hasta el extremo rojo y la longitud desde el punto de apoyo hasta el extremo azul
  • El número de la varilla suspendida del extremo rojo ($0$ si se suspende una pesa)
  • El número de la varilla suspendida del extremo azul ($0$ si se suspende una pesa)

Leyenda de los 2 diagramas de arriba — Izquierda (varilla número $1$): El móvil más ligero con esta estructura; Derecha (varilla número $1$): Un móvil que no es el más ligero.

Entrada

En la $1$.ª línea está escrito el número de varillas $n$ utilizadas en el móvil. En las siguientes $n$ líneas ($1 \le n \le 100$) están escritos los datos de cada varilla. En la línea $i + 1$ ($1 \le i \le n$) están escritos $4$ enteros $p, q, r, b$ separados por espacios, lo que indica que en la varilla $i$, la razón entre la longitud desde el punto de apoyo hasta el extremo rojo y la longitud desde el punto de apoyo hasta el extremo azul es $p : q$, el número de la varilla suspendida del extremo rojo es $r$, y el número de la varilla suspendida del extremo azul es $b$. Aquí, el número de varilla $0$ indica que se suspende una pesa. Además, en cualquier entrada, si $w$ es el valor mínimo del peso del móvil y $L$ es el valor máximo de los enteros positivos utilizados en la entrada para representar las razones, se cumple que $w L < 2^{31}$.

Salida

La salida consta de $1$ sola línea, en la que se imprime el peso del móvil.

Ejemplos de entrada y salida

Ejemplo de entrada 1

1
6 9 0 0

Ejemplo de salida 1

5

Ejemplo de entrada 2

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

Ejemplo de salida 2

40