โมบาย (Mobile) เป็นที่รู้จักอย่างแพร่หลายในฐานะงานศิลปะที่เคลื่อนไหวได้ คณะกรรมการ 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