Есептің шарты

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. Дәл $450$ уақыт мезетінде $0$ нүктесіне жетесіз, сондықтан $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