가장 가벼운 모빌

모빌(mobile)은 움직이는 예술품으로 널리 사랑받는다. 정보 올림피아드를 홍보하기 위해 조직 위원회에서 모빌을 만들기로 했다. 모빌은 막대, 끈, 추의 세 종류의 부품으로 다음 규칙에 따라 구성된다.

• 막대의 한쪽 끝은 파란색, 다른 쪽 끝은 빨간색으로 칠해져 있다.
• 막대는 두 끝점 사이의 한 지점(받침점)에서 끈으로 매달린다.
• 받침점에서 빨간 끝까지의 길이와 받침점에서 파란 끝까지의 길이는 모두 양의 정수이다.
• 막대의 양쪽 끝에는 각각 추 또는 다른 막대가 끈으로 매달린다.
• 추는 어떤 막대의 한쪽 끝에 끈으로 매달린다.
• 추 아래에는 아무것도 매달지 않는다.
• 추의 무게는 양의 정수이다.
• 끈 중 정확히 하나는 한쪽 끝이 어떤 막대의 받침점에 묶여 그 막대를 매달고, 다른 쪽 끝은 어떤 부품과도 묶여 있지 않다. 나머지 끈은 모두 다음 중 하나를 만족한다.
  • 어떤 막대의 끝과 다른 막대의 받침점을 잇는다.
  • 어떤 막대의 끝과 추를 잇는다.

단, 모든 막대는 균형이 잡혀 있어야 한다. 막대와 끈의 무게는 무시할 수 있을 만큼 가벼우므로 모두 $0$으로 간주한다. 즉, 각 막대에 대하여

$$(\text{빨간 끝 아래에 매달린 추 무게의 합}) \times (\text{받침점에서 빨간 끝까지의 길이}) = (\text{파란 끝 아래에 매달린 추 무게의 합}) \times (\text{받침점에서 파란 끝까지의 길이})$$

일 때 그 막대는 균형이 잡혀 있다고 한다.

간단한 모빌의 예	균형이 맞지 않아 모빌이 아닌 예
모빌의 예	모빌이 아닌 예

어떤 막대를 써서 어떻게 연결해 모빌을 구성할지는 이미 정해져 있지만, 추의 무게는 아직 정해지지 않았다. 가벼운 모빌일수록 매달기 쉬우므로 되도록 가벼운 모빌을 만들고 싶다. 모든 막대의 균형을 유지하면서 모빌의 총무게가 최소가 되도록 각 추에 양의 정수 무게를 정하고, 그때의 총무게를 출력하여라. 모빌의 구성 정보는 다음과 같이 주어진다.

• 막대의 개수 $n$
• 각 막대의 정보(막대 번호는 $1$부터 $n$까지): 받침점에서 빨간 끝까지의 길이와 파란 끝까지의 길이의 비, 빨간 끝에 매다는 막대의 번호(추를 매달면 $0$), 파란 끝에 매다는 막대의 번호(추를 매달면 $0$)

이 구성에서 가장 가벼운 모빌	가장 가볍지 않은 모빌

첫째 줄에 막대의 개수 $n$ ($1 \le n \le 100$)이 주어진다. 이어지는 $n$개의 줄에는 각 막대의 정보가 주어진다. $i+1$번째 줄 ($1 \le i \le n$)에는 네 정수 $p$, $q$, $r$, $b$가 공백으로 구분되어 주어진다. 막대 $i$에서 받침점에서 빨간 끝까지의 길이와 파란 끝까지의 길이의 비가 $p : q$이고, 빨간 끝에 매다는 막대의 번호가 $r$, 파란 끝에 매다는 막대의 번호가 $b$임을 뜻한다. 막대 번호 $0$은 그 자리에 추를 매단다는 뜻이다. 모든 입력에서, 모빌 무게의 최솟값을 $w$, 입력에서 비를 나타내는 데 쓰인 양의 정수의 최댓값을 $L$이라 할 때 $wL < 2^{31}$을 만족한다.

한 줄에 모빌의 최소 총무게를 출력한다.