תיאור הבעיה

חוות Just Oishi Ichigo (להלן חוות JOI) היא חוות תותים המפורסמת בכך שהיא ארוכה וצרה ממזרח למערב, והכניסה אליה נמצאת בנקודה המערבית ביותר של החווה. להלן, המקום הנמצא במרחק $k$ מטרים מזרחית לכניסה ייקרא נקודה $k$.

בתוך חוות JOI גדלים $N$ תותים. הם ממוספרים מ-$1$ עד $N$. כל התותים ירוקים עד זמן $0$. תות $i$ ($1 \le i \le N$) גדל בנקודה $A_{i}$, ובזמן $T_{i}$ הוא מבשיל והופך לאדום.

לא ניתן לקטוף תותים כשהם ירוקים. כלומר, לא ניתן לקטוף את תות $i$ עד זמן $T_{i}$. אתם יוצאים בזמן $0$ מהכניסה לחווה הנמצאת בנקודה $0$, ונעים בכיוון מזרח-מערב במהירות מרבית של $1$ מטר לשנייה תוך כדי קטיפת תותים. ניתן להזניח את הזמן הדרוש לקטיפת תות.

בהינתן המידע על חוות התותים, כתבו תוכנית המוצאת את הזמן המזערי הדרוש כדי לקטוף את כל התותים במצב אדום ולחזור אל הכניסה.

מגבלות

• $1 \le N \le 100\,000$.
• $0 \le A_{i} \le 1\,000\,000\,000 (= 10^{9})$ ($1 \le i \le N$).
• $0 \le T_{i} \le 1\,000\,000\,000 (= 10^{9})$ ($1 \le i \le N$).
• כל ערכי הקלט הם מספרים שלמים.

קלט

הקלט ניתן מהקלט הסטנדרטי בפורמט הבא:

N
A_1 T_1
A_2 T_2
:
A_N T_N

פלט

הדפיסו בשורה $1$ את הזמן המזערי הדרוש כדי לקטוף את כל התותים במצב אדום ולחזור אל הכניסה.

דוגמה 1

קלט

10
1 3
2 1
3 4
4 1
5 5
6 9
7 2
8 6
9 5
10 3

פלט

20

אם נעים במשך $10$ השניות הראשונות עד נקודה $10$, אפשר לקטוף בדרך את התותים $2, 4, 5, 7, 8, 9, 10$ בסדר זה. לאחר מכן, אם חוזרים במשך $10$ שניות לנקודה $0$, אפשר לקטוף בדרך את התותים $6, 3, 1$ בסדר זה. כך ניתן לקטוף את כל $10$ התותים במצב אדום.

דוגמה 2

קלט

10
0 450
5 445
10 430
15 405
20 370
25 325
30 270
35 205
40 130
45 45

פלט

450

אם נעים באופן הבא, ניתן לקטוף את כל התותים במצב אדום תוך $450$ שניות:

1. נעים במשך $45$ שניות עד נקודה $45$. מכיוון שכעת הזמן הוא $45$, ניתן לקטוף את תות $10$. לאחר הקטיפה נעים במשך $45$ שניות חזרה לנקודה $0$.
2. לאחר מכן, נעים במשך $40$ שניות עד נקודה $40$. מכיוון שכעת הזמן הוא $130$, ניתן לקטוף את תות $9$. לאחר הקטיפה נעים במשך $40$ שניות חזרה לנקודה $0$.
3. לאחר מכן, נעים במשך $35$ שניות עד נקודה $35$. מכיוון שכעת הזמן הוא $205$, ניתן לקטוף את תות $8$. לאחר הקטיפה נעים במשך $35$ שניות חזרה לנקודה $0$.
4. לאחר מכן, נעים במשך $30$ שניות עד נקודה $30$. מכיוון שכעת הזמן הוא $270$, ניתן לקטוף את תות $7$. לאחר הקטיפה נעים במשך $30$ שניות חזרה לנקודה $0$.
5. לאחר מכן, נעים במשך $25$ שניות עד נקודה $25$. מכיוון שכעת הזמן הוא $325$, ניתן לקטוף את תות $6$. לאחר הקטיפה נעים במשך $25$ שניות חזרה לנקודה $0$.
6. לאחר מכן, נעים במשך $20$ שניות עד נקודה $20$. מכיוון שכעת הזמן הוא $370$, ניתן לקטוף את תות $5$. לאחר הקטיפה נעים במשך $20$ שניות חזרה לנקודה $0$.
7. לאחר מכן, נעים במשך $15$ שניות עד נקודה $15$. מכיוון שכעת הזמן הוא $405$, ניתן לקטוף את תות $4$. לאחר הקטיפה נעים במשך $15$ שניות חזרה לנקודה $0$.
8. לאחר מכן, נעים במשך $10$ שניות עד נקודה $10$. מכיוון שכעת הזמן הוא $430$, ניתן לקטוף את תות $3$. לאחר הקטיפה נעים במשך $10$ שניות חזרה לנקודה $0$.
9. לאחר מכן, נעים במשך $5$ שניות עד נקודה $5$. מכיוון שכעת הזמן הוא $445$, ניתן לקטוף את תות $2$. לאחר הקטיפה נעים במשך $5$ שניות חזרה לנקודה $0$.
10. מגיעים לנקודה $0$ בדיוק בזמן $450$, ולכן ניתן לקטוף את תות $1$. הגענו לנקודה $0$ בדיוק באותו זמן שבו סיימנו לקטוף את כל התותים.

דוגמה 3

קלט

15
11 23
3 94
89 3
38 58
65 29
41 3
80 42
22 76
48 85
83 98
87 29
97 96
22 75
57 25
99 33

פלט

198