يحضر الصغير 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$.