D הקטן מתכונן למסע מסביב לעולם. לפני היציאה, עליו להשלים לפי התוכנית $n$ פעולות של הכנת אספקה מהרשימה שלו, כאשר פעולות אלו ממוספרות בהתחלה לפי הסדר $1, 2, \dots, n$.
נסמן את כמות האספקה הנוכחית במספר שלם $x$, כאשר בהתחלה $x = 0$. הפעולה ה-$i$ מתוארת על ידי שני מספרים שלמים חיוביים $a_i, b_i$, ובעת ביצוע פעולה זו מתרחשים בזה אחר זה השינויים הבאים:
- תחילה מגדילים את $x$ ב-$a_i$ (כלומר מציבים $x \leftarrow x + a_i$);
- לאחר מכן בודקים את גודלו של $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$ נקודות, וכל מקרה בדיקה מוערך בנפרד. טווחי הנתונים המפורטים מופיעים בטבלה שלהלן.
| מספר מקרה בדיקה | $n$ | תכונה מיוחדת | ניקוד למקרה |
|---|---|---|---|
| $1 \sim 4$ | $\le 2000$ | ללא | $10$ |
| $5 \sim 6$ | $\le 2 \times 10^5$ | A | $10$ |
| $7 \sim 10$ | $\le 2 \times 10^5$ | ללא | $10$ |
תכונה מיוחדת A: $b_1 = b_2 = \dots = b_n$.