เสี่ยว D กำลังเตรียมตัวสำหรับการเดินทางรอบโลก ก่อนออกเดินทาง เขาต้องดำเนินการเตรียมเสบียงตามรายการทั้งหมด $n$ รายการตามแผน โดยการดำเนินการเหล่านี้เริ่มต้นจะถูกกำหนดหมายเลขตามลำดับเป็น $1, 2, \dots, n$

ให้จำนวนเสบียงในปัจจุบันเป็นจำนวนเต็ม $x$ โดยเริ่มต้นที่ $x = 0$ การดำเนินการลำดับที่ $i$ อธิบายด้วยจำนวนเต็มบวกสองจำนวนคือ $a_i, b_i$ เมื่อดำเนินการดังกล่าวจะเกิดการเปลี่ยนแปลงตามลำดับดังนี้:

1. ขั้นแรก เพิ่มค่า $x$ ขึ้นอีก $a_i$ (กล่าวคือกำหนดให้ $x \leftarrow x + a_i$);
2. จากนั้นตรวจสอบขนาดของ $x$: หากในขณะนั้น $x > b_i$ ให้ลดค่า $x$ ลงเหลือ $b_i$ (กล่าวคือกำหนดให้ $x \leftarrow \min(x, b_i)$)

ก่อนที่จะเริ่มดำเนินการ เสี่ยว D สามารถปรับเปลี่ยนลำดับในรายการได้มากที่สุดหนึ่งครั้ง: เลือกการดำเนินการใดการดำเนินการหนึ่ง นำออกมาแล้วย้ายไปไว้ที่ท้ายสุดของลำดับ โดยที่ลำดับสัมพัทธ์ของการดำเนินการที่เหลือยังคงเดิม (หรือจะเลือกไม่ปรับเปลี่ยนเลยก็ได้)

หลังจากปรับเปลี่ยนเสร็จแล้ว เสี่ยว D จะดำเนินการทั้ง $n$ รายการตามลำดับใหม่จากหน้าไปหลังตามลำดับ โดยแต่ละการดำเนินการจะทำเพียงครั้งเดียวเท่านั้น เสี่ยว D อยากทราบว่า หลังจากดำเนินการทั้งหมดเสร็จสิ้นแล้ว จำนวนเสบียง $x$ จะมีค่ามากที่สุดได้เท่าใด?

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

อ่านข้อมูลจาก stdin

บรรทัดแรกประกอบด้วยจำนวนเต็มบวก $n$ แทนจำนวนการดำเนินการ

อีก $n$ บรรทัดถัดไป บรรทัดที่ $i$ ประกอบด้วยจำนวนเต็มบวกสองจำนวนคือ $a_i, b_i$ อธิบายพารามิเตอร์ของการดำเนินการลำดับที่ $i$

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

ส่งออกไปยัง stdout

แสดงผลหนึ่งบรรทัดเป็นจำนวนเต็มหนึ่งจำนวน แทนค่ามากที่สุดที่เป็นไปได้ของจำนวนเสบียง $x$ หลังจากดำเนินการทั้งหมดเสร็จสิ้น

ตัวอย่าง

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

3
1 100
100 90
1 1

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

90

หมายเหตุ

ย้ายการดำเนินการลำดับที่ $2$ ไปไว้ท้ายลำดับ ลำดับการดำเนินการจะกลายเป็น $1, 3, 2$ หลังจากการดำเนินการแต่ละรายการเสร็จสิ้น ค่าของ $x$ จะเปลี่ยนเป็น $1, 1, 90$ ตามลำดับ

หากย้ายการดำเนินการลำดับที่ $1$ ไปไว้ท้ายสุด ค่าสุดท้ายคือ $x = 2$; หากไม่ปรับลำดับหรือย้ายการดำเนินการลำดับที่ $3$ ไปไว้ท้ายสุด ค่าสุดท้ายคือ $x = 1$ ดังนั้นค่ามากที่สุดที่เป็นไปได้ของ $x$ คือ $90$

ตัวอย่าง 2

ดูที่ไฟล์ supply/supply2.in และ supply/supply2.ans ในไดเรกทอรีของผู้เข้าแข่งขัน

ตัวอย่างนี้สอดคล้องกับเงื่อนไขข้อจำกัดของชุดทดสอบที่ $1 \sim 4$

ตัวอย่าง 3

ดูที่ไฟล์ supply/supply3.in และ supply/supply3.ans ในไดเรกทอรีของผู้เข้าแข่งขัน

ตัวอย่างนี้สอดคล้องกับเงื่อนไขข้อจำกัดของชุดทดสอบที่ $5 \sim 6$

ตัวอย่าง 4

ดูที่ไฟล์ supply/supply4.in และ supply/supply4.ans ในไดเรกทอรีของผู้เข้าแข่งขัน

ตัวอย่างนี้สอดคล้องกับเงื่อนไขข้อจำกัดของชุดทดสอบที่ $7 \sim 10$

ข้อจำกัด

สำหรับข้อมูลทั้งหมด รับประกันว่า $1 \le n \le 2 \times 10^5$ และ $1 \le a_i, b_i \le 10^9$ โปรดทราบว่า: ข้อมูลไม่รับประกันว่า $a_i \le b_i$

โจทย์ข้อนี้มีชุดทดสอบทั้งหมด $10$ ชุด ชุดละ $10$ คะแนน โดยแต่ละชุดทดสอบคิดคะแนนแยกกันอย่างอิสระ ขอบเขตข้อมูลโดยละเอียดแสดงในตารางด้านล่าง

คุณสมบัติพิเศษ A: $b_1 = b_2 = \dots = b_n$