모빌은 움직이는 예술품으로 널리 사랑받고 있다. 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