1117 : ภารกิจ (mission)
Problem type : Batch
Time limit : 1.0 second(s)
Memory limit : 32 megabyte(s)
ในเกมออนไลน์ชนิดหนึ่ง มีภารกิจให้ทำอยู่ N ชนิด ในการทำภารกิจแต่ละภารกิจจะใช้พลังงานในการทำแตกต่างกัน และเมื่อทำเสร็จแล้ว จะได้รับค่าประสบการณ์แตกต่างกัน โดยภารกิจชนิดที่ i จะใช้พลังงาน Ai และเมื่อทำเสร็จแล้วจะได้รับค่าประสบการณ์ Bi คุณสามารถเลือกทำภารกิจกี่อย่างก็ได้ (หรือไม่ทำเลยก็ได้) หลังจากทำภารกิจทั้งหมดเสร็จ คุณจะได้คะแนนเท่ากับค่าประสบการณ์รวมทั้งหมดที่ได้ ลบด้วยสองเท่าของพลังงานรวมทั้งหมดที่ใช้ไป นอกจากนี้ คุณยังจะต้องเสียค่าปรับสำหรับภารกิจที่คุณไม่ได้ทำ โดยคุณจะถูกลบคะแนนเท่ากับกำลังสองของจำนวนภารกิจที่ไม่ได้ทำ คุณต้องการเลือกทำภารกิจเพื่อให้ได้คะแนนรวมมากที่สุดเท่าที่จะทำได้

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

ข้อมูลนำเข้า
บรรทัดแรกระบุจำนวนเต็ม N (1 ≤ N ≤ 100,000)

อีก N บรรทัดต่อมา ในบรรทัดที่ i+1 (1 
≤ i ≤ N) ระบุจำนวนเต็ม Ai (1 ≤ Ai ≤ 1,000,000) และ Bi (1 ≤ Bi ≤ 1,000,000) แทนพลังงานที่ใช้และค่าประสบการณ์ที่ได้รับจากภารกิจที่ i

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

การให้คะแนน

20% ของข้อมูลทดสอบ จะมี N ≤ 10
50% ของข้อมูลทดสอบ จะมี N ≤ 1,000

ที่มา

การแข่งขัน TUMSO ครั้งที่ 8
โจทย์โดย: สุธี เรืองวิเศษ
 

ตัวอย่างข้อมูลนำเข้า ตัวอย่างข้อมูลส่งออก
3
3 10
4 10
5 10
6
4
6 10
6 20
8 10
8 20
9

ความช่วยเหลือ: ไม่มีคำใบ้สำหรับปัญหานี้

กำลังออนไลน์: 19 ผู้เยี่ยมชมและ 1 สมาชิก (1 บอท)