Đồ treo cân bằng (Mobile) được yêu thích rộng rãi như một tác phẩm nghệ thuật chuyển động. Ủy ban IOI Nhật Bản đã quyết định làm một chiếc đồ treo để quảng bá cho JOI. Chiếc đồ treo quảng bá JOI được cấu tạo như sau bằng cách sử dụng $3$ loại phần tử: thanh ngang, dây treo và quả nặng.

• Một đầu của mỗi thanh được sơn màu xanh lam, đầu kia được sơn màu đỏ.
• Mỗi thanh được treo bằng một sợi dây tại $1$ điểm nằm ngoài hai đầu của nó làm điểm tựa.
• Độ dài từ điểm tựa đến đầu màu đỏ cũng như độ dài từ điểm tựa đến đầu màu xanh lam đều là các số nguyên dương.
• Ở hai đầu của mỗi thanh, người ta dùng dây để treo một quả nặng hoặc một thanh khác.
• Mỗi quả nặng được treo bằng dây vào một đầu của một thanh nào đó.
• Không có vật gì được treo bên dưới quả nặng.
• Trọng lượng của mỗi quả nặng là một số nguyên dương.
• Trong số các sợi dây, chỉ có đúng $1$ sợi dây có một đầu được buộc vào điểm tựa của một thanh nào đó để treo thanh đó lên, còn đầu kia không buộc vào bất kỳ phần tử cấu thành nào khác. Tất cả các sợi dây khác đều thỏa mãn một trong hai điều kiện sau:
  • Nối một đầu của một thanh nào đó với điểm tựa của một thanh nào đó.
  • Nối một đầu của một thanh nào đó với một quả nặng nào đó.

Tuy nhiên, mọi thanh đều phải ở trạng thái cân bằng. Vì trọng lượng của các thanh và dây nhẹ đến mức có thể bỏ qua, hãy giải bài toán với giả thiết trọng lượng của tất cả các thanh và dây đều bằng $0$. Nói cách khác, đối với mỗi thanh, thanh đó được coi là cân bằng khi:

(tổng trọng lượng các quả nặng được treo phía dưới đầu đỏ của thanh đó) $\times$ (độ dài từ điểm tựa của thanh đó đến đầu đỏ) $=$ (tổng trọng lượng các quả nặng được treo phía dưới đầu xanh của thanh đó) $\times$ (độ dài từ điểm tựa của thanh đó đến đầu xanh)

Chú thích cho 4 hình bên trên — Trên bên trái: Ví dụ về đồ treo đơn giản; Trên bên phải: Ví dụ không phải là đồ treo vì không cân bằng; Dưới bên trái: Ví dụ về đồ treo; Dưới bên phải: Ví dụ không phải là đồ treo.

Việc sử dụng các thanh có độ dài như thế nào và buộc chúng ra sao để tạo thành đồ treo đã được quyết định sẵn, nhưng trọng lượng của các quả nặng thì vẫn chưa được quyết định. Vì đồ treo càng nhẹ thì càng dễ treo, ta muốn làm một chiếc đồ treo nhẹ nhất có thể. Như đã mô tả ở trên, hãy viết chương trình tìm cách gắn các quả nặng sao cho tổng trọng lượng của đồ treo là nhỏ nhất trong khi vẫn giữ cho mọi thanh đều cân bằng, và in ra tổng trọng lượng của đồ treo khi đó. Chương trình được cung cấp các thông tin sau đây về cấu trúc của đồ treo:

• Số lượng thanh $n$
• Thông tin của từng thanh (các thanh được đánh số từ $1$ đến $n$):
  • Tỷ lệ giữa độ dài từ điểm tựa đến đầu đỏ và độ dài từ điểm tựa đến đầu xanh
  • Số hiệu của thanh được treo ở đầu đỏ (bằng $0$ nếu treo quả nặng)
  • Số hiệu của thanh được treo ở đầu xanh (bằng $0$ nếu treo quả nặng)

Chú thích cho 2 hình bên trên — Trái (Thanh số $1$): Đồ treo nhẹ nhất với cấu trúc này; Phải (Thanh số $1$): Đồ treo không phải nhẹ nhất.

Dữ liệu vào

Dòng thứ $1$ chứa số lượng thanh $n$ được sử dụng trong đồ treo. $n$ dòng tiếp theo ($1 \le n \le 100$) chứa dữ liệu của từng thanh. Dòng thứ $i + 1$ ($1 \le i \le n$) chứa $4$ số nguyên $p, q, r, b$ cách nhau bởi khoảng trắng, cho biết đối với thanh $i$, tỷ lệ giữa độ dài từ điểm tựa đến đầu đỏ và độ dài từ điểm tựa đến đầu xanh là $p : q$, số hiệu của thanh được treo ở đầu đỏ là $r$, và số hiệu của thanh được treo ở đầu xanh là $b$. Lưu ý rằng thanh số $0$ biểu thị việc treo một quả nặng. Ngoài ra, trong mọi dữ liệu vào, nếu gọi giá trị nhỏ nhất của trọng lượng đồ treo là $w$ và giá trị lớn nhất của các số nguyên dương dùng để biểu diễn tỷ lệ trong dữ liệu vào là $L$, thì luôn thỏa mãn $w L < 2^{31}$.

Kết quả

Kết quả chỉ gồm $1$ dòng duy nhất, in ra trọng lượng của đồ treo.

Ví dụ vào/ra

Dữ liệu vào 1

1
6 9 0 0

Kết quả 1

5

Dữ liệu vào 2

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

Kết quả 2

40