หลังจากคุณหยุดระบบรักษาความปลอดภัยที่ทำงานกะทันหันจากความผิดพลาดของตัวคุณเองได้สำเร็จ ถึงเวลาแล้วที่จะต้องหาแผนการใหม่ หลังจากครุ่นคิดอยู่ชั่วครู่ แผนการอันแยบยลก็ผุดขึ้นมาในสมองคุณ นั่นคือ การถล่มด้วยหนอน !

            แต่แล้วปัญหาก็เกิดขึ้นอีกแล้ว เมื่อคุณพบว่า ในการยิงหนอนแต่ละตัวนั้น ต้องใช้ค่าไฟมากยิ่งขึ้นไปอีก เหล่สายตาไปมองตัวเลขบนบิลค่าไฟที่อยู่ข้าง ๆ ตัว นั่นทำให้คุณตกที่นั่งลำบากอีกเสียแล้ว

            คุณมีหนอนอยู่ทั้งหมด N ตัว แต่ละตัวมีค่าไฟในการยิงและจำนวนข้อมูลที่สามารถทำลายได้แตกต่างกันไป การคิดค่าไฟในการยิงหนึ่งครั้ง จะคิดโดยคิดตามค่าไฟของหนอนตัวที่มีมูลค่ามากที่สุด ตัวอย่างเช่น ถ้ามีหนอน 5 ตัว มีจำนวนข้อมูลที่ทำลายได้และค่าไฟ ดังนี้

            ถ้าเลือกยิงหนอนตัวที่ 1, 3, 5 ซึ่งใช้ค่าไฟ 30, 20, 70 ตามลำดับ จะต้องเสียค่าไฟในการยิงทั้งหมด 70 หน่วย แต่ถ้าเลือกยิงหนอนตัวที่ 3, 4 ซึ่งใช้ค่าไฟ 20, 50 ตามลำดับ จะต้องเสียค่าไฟในการยิงทั้งหมด 50 หน่วย

            คุณสามารถนิยามอัตราส่วนความคุ้มค่าของการยิงหนอน ให้มีค่าเท่ากับ จำนวนข้อมูลที่ทำลายได้ทั้งหมด หารด้วย ค่าไฟที่ใช้ในการยิง ซึ่งแน่นอนว่า คุณไม่ต้องการจะเสียค่าไฟให้เยอะกว่าเดิมโดยเปล่าประโยชน์

งานของคุณ

เขียนโปรแกรมที่รับข้อมูลของหนอนทั้งหมด N ตัว และคำนวณหาอัตราส่วนความคุ้มค่าที่มากที่สุดที่เป็นไปได้

ข้อมูลนำเข้า

บรรทัดที่ 1 มีจำนวนเต็ม N (1 ≤ N ≤ 100,000) แทนจำนวนของหนอน

บรรทัดที่ 2 ถึง N + 1 ประกอบด้วยจำนวนเต็ม D_i และ C_i (0 ≤ D_i ≤ 50,000 และ 1 ≤ C_i ≤ 800,000,000) แทนจำนวนข้อมูลที่ทำลายได้ และค่าไฟที่ใช้ในการยิงของหนอนตัวที่ i ตามลำดับ

ข้อมูลส่งออก

บรรทัดที่ 1 แสดงจำนวนข้อมูลที่คุณสามารถทำลายได้ทั้งหมด และค่าไฟที่ใช้ในการยิง คั่นด้วยช่องว่าง 1 ช่อง ในวิธีที่มีอัตราส่วนความคุ้มค่าที่มากที่สุด

หมายเหตุ หากมีวิธีค่าส่งหลายวิธีให้ตอบวิธีที่ใช้ค่าไฟน้อยที่สุด

อธิบายตัวอย่างข้อมูลนำเข้าและส่งออกที่ 1

ถ้าเลือกยิงหนอนตัวที่ 2 และ 3 จะสามารถทำลายข้อมูลได้รวมเท่ากับ 16 และเสียค่าไฟ 20 หน่วย ซึ่งมีอัตราส่วนความคุ้มค่า = 0.80 ซึ่งเป็นค่าที่มากที่สุดในการยิงหนอนครั้งนี้

การให้คะแนน

30% ของชุดข้อมูลทดสอบมีค่า 1 ≤ N ≤ 20,000 สำหรับชุดข้อมูลทดสอบทั้งหมด N ≤ 100,000

โจทย์โดย: ศรัณย์ ไพศาลศรีสมสุข

ที่มา: TOI.C:01-2009