Một tác phẩm treo chuyển động (mobile) là một vật trang trí phổ biến có các bộ phận có thể chuyển động. Ủy ban Olympic Tin học Nhật Bản muốn làm một tác phẩm như vậy để quảng bá JOI.

Tác phẩm được tạo bởi các thanh, dây và quả nặng theo những quy tắc sau:

• Mỗi thanh có một đầu màu đỏ và một đầu màu xanh lam.
• Mỗi thanh được treo bằng một sợi dây tại một điểm tựa nằm giữa hai đầu thanh, không trùng với đầu nào.
• Khoảng cách từ điểm tựa đến đầu đỏ và từ điểm tựa đến đầu xanh lam đều là số nguyên dương.
• Tại mỗi đầu thanh, một sợi 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; không có gì được treo bên dưới quả nặng.
• Khối lượng của mỗi quả nặng là một số nguyên dương.
• Có đúng một sợi dây có một đầu buộc vào điểm tựa của một thanh và đầu còn lại không buộc vào bộ phận nào khác. Mọi sợi dây còn lại đều nối một đầu thanh với điểm tựa của một thanh khác, hoặc nối một đầu thanh với một quả nặng.

Mọi thanh đều phải cân bằng. Bỏ qua khối lượng của thanh và dây, tức coi chúng có khối lượng bằng \(0\). Với một thanh, gọi \(W_{\text{đỏ}}\) và \(W_{\text{xanh lam}}\) lần lượt là tổng khối lượng của tất cả các quả nặng treo bên dưới đầu đỏ và đầu xanh lam; gọi \(L_{\text{đỏ}}\) và \(L_{\text{xanh lam}}\) là khoảng cách từ điểm tựa đến hai đầu tương ứng. Thanh cân bằng khi và chỉ khi

Cấu trúc nối các thanh và tỉ lệ độ dài hai phía của mỗi thanh đã được xác định, nhưng khối lượng các quả nặng chưa được chọn. Tác phẩm càng nhẹ thì càng dễ thao tác.

Chẳng hạn, với một thanh có hai cánh tay đòn theo tỉ lệ \(6:9\), treo quả nặng khối lượng \(3\) ở đầu đỏ và quả nặng khối lượng \(2\) ở đầu xanh lam thì thanh cân bằng vì \(3 \times 6 = 2 \times 9\). Đây là cách tạo tác phẩm nhẹ nhất với cấu trúc này, có tổng khối lượng \(5\).

Nếu hai khối lượng lần lượt là \(2\) và \(3\), thanh không cân bằng nên không tạo thành một tác phẩm hợp lệ. Nếu hai khối lượng lần lượt là \(9\) và \(6\), thanh vẫn cân bằng nhưng tổng khối lượng là \(15\), không phải nhỏ nhất.

Yêu cầu

Chọn khối lượng nguyên dương cho các quả nặng sao cho mọi thanh đều cân bằng và tổng khối lượng của tác phẩm là nhỏ nhất. In ra tổng khối lượng nhỏ nhất đó.

Dữ liệu vào

Đọc từ đầu vào chuẩn:

• Dòng đầu tiên chứa số nguyên \(n\), là số thanh. Các thanh được đánh số từ \(1\) đến \(n\).
• Dòng thứ \(i+1\) (\(1 \le i \le n\)) chứa bốn số nguyên \(p,q,r,b\), cách nhau bởi dấu cách, mô tả thanh \(i\).
• Tỉ lệ giữa khoảng cách từ điểm tựa đến đầu đỏ và khoảng cách từ điểm tựa đến đầu xanh lam là \(p:q\).
• \(r\) là số hiệu thanh treo ở đầu đỏ; \(b\) là số hiệu thanh treo ở đầu xanh lam. Giá trị \(0\) cho biết tại đầu tương ứng treo một quả nặng thay vì một thanh.

Dữ liệu ra

Ghi ra đầu ra chuẩn một dòng chứa một số nguyên là tổng khối lượng nhỏ nhất của tác phẩm.

Ràng buộc

• \(1 \le n \le 100\).
• \(p,q\) là các số nguyên dương.
• \(0 \le r,b \le n\).
• Dữ liệu mô tả cấu trúc của một tác phẩm theo đúng các quy tắc đã nêu. Thanh trên cùng không nhất thiết là thanh số \(1\).
• Gọi \(w\) là tổng khối lượng nhỏ nhất và \(L\) là giá trị lớn nhất trong tất cả các số \(p,q\) xuất hiện trong đầu vào. Luôn có \(wL < 2^{31}\).

Phân nhóm

Bài có tổng cộng \(20\) điểm, gồm \(15\) test chia thành \(10\) nhóm. Mỗi nhóm được \(2\) điểm khi tất cả test trong nhóm đều đúng, ngược lại được \(0\) điểm. Mọi nhóm đều dùng các ràng buộc chung ở trên.

1. Nhóm 1 (\(2\) điểm): test \(1\) và \(2\).
2. Nhóm 2 (\(2\) điểm): test \(3\) và \(4\).
3. Nhóm 3 (\(2\) điểm): test \(5\) và \(6\).
4. Nhóm 4 (\(2\) điểm): test \(7\) và \(8\).
5. Nhóm 5 (\(2\) điểm): test \(9\) và \(10\).
6. Nhóm 6 (\(2\) điểm): test \(11\).
7. Nhóm 7 (\(2\) điểm): test \(12\).
8. Nhóm 8 (\(2\) điểm): test \(13\).
9. Nhóm 9 (\(2\) điểm): test \(14\).
10. Nhóm 10 (\(2\) điểm): test \(15\).

Ví dụ

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

40