Mobile cieszą się dużą popularnością jako ruchome dzieła sztuki. Japoński Komitet IOI postanowił wykonać mobil w celu promocji JOI. Mobil promocyjny JOI jest zbudowany w następujący sposób z $3$ rodzajów elementów: prętów, sznurków oraz ciężarków.

• Jeden koniec każdego pręta jest pomalowany na niebiesko, a drugi koniec na czerwono.
• Każdy pręt jest zawieszony na sznurku w $1$ punkcie innym niż jego dwa końce, stanowiącym punkt podparcia.
• Zarówno długość od punktu podparcia do czerwonego końca, jak i długość od punktu podparcia do niebieskiego końca są dodatnimi liczbami całkowitymi.
• Na obu końcach pręta zawiesza się na sznurku ciężarek albo inny pręt.
• Każdy ciężarek jest zawieszony na sznurku na jednym z końców pewnego pręta.
• Do ciężarka nic nie jest podwieszone.
• Ciężar każdego ciężarka jest dodatnią liczbą całkowitą.
• Dokładnie $1$ ze sznurków ma jeden koniec przywiązany do punktu podparcia pewnego pręta w celu zawieszenia tego pręta, natomiast jego drugi koniec nie jest przywiązany do żadnego innego elementu składowego. Wszystkie pozostałe sznurki spełniają jeden z poniższych warunków:
  • Łączy koniec pewnego pręta z punktem podparcia pewnego pręta.
  • Łączy koniec pewnego pręta z pewnym ciężarkiem.

Każdy pręt musi jednak pozostawać w równowadze. Ponieważ ciężar prętów i sznurków jest pomijalnie mały, rozwiąż zadanie przy założeniu, że ciężary wszystkich prętów i sznurków wynoszą $0$. Innymi słowy, dla każdego pręta uznajemy, że jest on w równowadze, gdy:

(suma ciężarów ciężarków zawieszonych poniżej czerwonego końca tego pręta) $\times$ (długość od punktu podparcia tego pręta do czerwonego końca) $=$ (suma ciężarów ciężarków zawieszonych poniżej niebieskiego końca tego pręta) $\times$ (długość od punktu podparcia tego pręta do niebieskiego końca)

Opis 4 powyższych rysunków — Lewy górny: Przykład prostego mobilu; Prawy górny: Przykład niebędący mobilem, ponieważ nie jest w równowadze; Lewy dolny: Przykład mobilu; Prawy dolny: Przykład niebędący mobilem.

To, jakiej długości pręty i w jaki sposób zostaną połączone, aby utworzyć mobil, zostało już ustalone, ale ciężary poszczególnych ciężarków nie zostały jeszcze określone. Ponieważ lżejszy mobil łatwiej zawiesić, chcemy wykonać mobil tak lekki, jak to tylko możliwe. Napisz program, który — tak jak opisano powyżej — wyznaczy sposób dobrania ciężarków minimalizujący całkowity ciężar mobilu przy zachowaniu równowagi każdego pręta i wypisze całkowity ciężar mobilu w tym przypadku. Program otrzymuje następujące informacje o budowie mobilu:

• Liczba prętów $n$
• Informacje dla każdego pręta (pręty są ponumerowane od $1$ do $n$):
  • Stosunek długości od punktu podparcia do czerwonego końca do długości od punktu podparcia do niebieskiego końca
  • Numer pręta zawieszonego na czerwonym końcu ($0$, jeśli zawieszony jest ciężarek)
  • Numer pręta zawieszonego na niebieskim końcu ($0$, jeśli zawieszony jest ciężarek)

Opis 2 powyższych rysunków — Po lewej (pręt nr $1$): Najlżejszy mobil o tej konstrukcji; Po prawej (pręt nr $1$): Mobil, który nie jest najlżejszy.

Wejście

W $1$. wierszu zapisana jest liczba prętów $n$ użytych w mobilu. W kolejnych $n$ wierszach ($1 \le n \le 100$) zapisane są dane poszczególnych prętów. W wierszu $i + 1$ ($1 \le i \le n$) zapisane są $4$ liczby całkowite $p, q, r, b$ oddzielone spacjami, oznaczające, że dla pręta $i$ stosunek długości od punktu podparcia do czerwonego końca do długości od punktu podparcia do niebieskiego końca wynosi $p : q$, numer pręta zawieszonego na czerwonym końcu to $r$, a numer pręta zawieszonego na niebieskim końcu to $b$. Przy tym numer pręta $0$ oznacza, że zawieszony jest ciężarek. Ponadto w każdym teście wejściowym, jeśli przez $w$ oznaczymy minimalną wartość ciężaru mobilu, a przez $L$ maksymalną wartość dodatnich liczb całkowitych użytych na wejściu do zapisania stosunków długości, to spełniona jest nierówność $w L < 2^{31}$.

Wyjście

Wyjście składa się z $1$ wiersza zawierającego ciężar mobilu.

Przykłady wejścia i wyjścia

Przykład wejścia 1

1
6 9 0 0

Przykład wyjścia 1

5

Przykład wejścia 2

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

Przykład wyjścia 2

40