Mobile (hiasan gantung bergerak) dikenal luas sebagai karya seni kinetik. Komite IOI Jepang memutuskan untuk membuat sebuah mobile guna mempromosikan JOI. Mobile promosi JOI disusun menggunakan $3$ jenis elemen, yaitu batang, tali, dan bandul pemberat, dengan cara sebagai berikut:

• Salah satu ujung batang dicat biru, dan ujung lainnya dicat merah.
• Setiap batang digantung dengan tali pada $1$ titik selain kedua ujungnya sebagai titik tumpu.
• Panjang dari titik tumpu ke ujung merah maupun panjang dari titik tumpu ke ujung biru merupakan bilangan bulat positif.
• Pada kedua ujung batang, digantungkan bandul atau batang lain dengan menggunakan tali.
• Setiap bandul digantungkan dengan tali pada salah satu ujung dari suatu batang.
• Tidak ada apa pun yang digantungkan pada bandul.
• Berat setiap bandul merupakan bilangan bulat positif.
• Tepat $1$ di antara tali-tali yang ada memiliki satu ujung yang diikatkan pada titik tumpu suatu batang untuk menggantung batang tersebut, sementara ujung lainnya tidak diikatkan pada elemen penyusun mana pun. Semua tali lainnya memenuhi salah satu dari kondisi berikut:
  • Menghubungkan ujung suatu batang dengan titik tumpu suatu batang.
  • Menghubungkan ujung suatu batang dengan suatu bandul.

Akan tetapi, setiap batang harus berada dalam keadaan seimbang. Karena berat batang dan tali sangat ringan sehingga dapat diabaikan, jawablah dengan menganggap berat semua batang dan tali adalah $0$. Dengan kata lain, untuk setiap batang, batang tersebut dianggap seimbang apabila:

(total berat bandul yang tergantung di bawah ujung merah batang tersebut) $\times$ (panjang dari titik tumpu batang tersebut ke ujung merah) $=$ (total berat bandul yang tergantung di bawah ujung biru batang tersebut) $\times$ (panjang dari titik tumpu batang tersebut ke ujung biru)

Keterangan untuk 4 gambar di atas — Kiri atas: Contoh mobile sederhana; Kanan atas: Contoh bukan mobile karena tidak seimbang; Kiri bawah: Contoh mobile; Kanan bawah: Contoh bukan mobile.

Batang dengan panjang berapa dan bagaimana cara menghubungkannya untuk menyusun mobile sudah ditentukan, namun berat dari bandul-bandulnya belum ditentukan. Karena mobile yang lebih ringan lebih mudah digantung, kita ingin membuat mobile yang seringan mungkin. Seperti yang dijelaskan di atas, buatlah program yang mencari cara memasang bandul sehingga meminimalkan total berat mobile sambil menjaga setiap batang tetap seimbang, lalu mengeluarkan total berat mobile pada saat itu. Program akan diberikan informasi mengenai susunan mobile sebagai berikut:

• Banyaknya batang $n$
• Informasi untuk setiap batang (nomor batang adalah dari $1$ sampai $n$):
  • Perbandingan panjang dari titik tumpu ke ujung merah dan panjang dari titik tumpu ke ujung biru
  • Nomor batang yang digantungkan pada ujung merah ($0$ jika yang digantungkan adalah bandul)
  • Nomor batang yang digantungkan pada ujung biru ($0$ jika yang digantungkan adalah bandul)

Keterangan untuk 2 gambar di atas — Kiri (Batang nomor $1$): Mobile paling ringan dengan susunan ini; Kanan (Batang nomor $1$): Mobile yang bukan paling ringan.

Masukan

Baris ke-$1$ berisi banyaknya batang $n$ yang digunakan dalam mobile. Sebanyak $n$ baris berikutnya ($1 \le n \le 100$) berisi data masing-masing batang. Baris ke-$i + 1$ ($1 \le i \le n$) berisi $4$ bilangan bulat $p, q, r, b$ yang dipisahkan oleh spasi, yang menyatakan bahwa pada batang $i$, perbandingan panjang dari titik tumpu ke ujung merah dengan panjang dari titik tumpu ke ujung biru adalah $p : q$, nomor batang yang digantungkan pada ujung merah adalah $r$, dan nomor batang yang digantungkan pada ujung biru adalah $b$. Di sini, nomor batang $0$ menyatakan bahwa yang digantungkan adalah bandul. Selain itu, pada setiap masukan, jika nilai minimum dari berat mobile adalah $w$ dan nilai maksimum dari bilangan bulat positif yang digunakan untuk menyatakan perbandingan dalam masukan adalah $L$, maka berlaku $w L < 2^{31}$.

Keluaran

Keluaran hanya terdiri dari $1$ baris, yaitu berat mobile tersebut.

Contoh Masukan dan Keluaran

Contoh Masukan 1

1
6 9 0 0

Contoh Keluaran 1

5

Contoh Masukan 2

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

Contoh Keluaran 2

40