Énoncé du problème

La ferme Just Oishi Ichigo (ci-après appelée ferme JOI) est une fraiseraie célèbre pour sa forme très allongée d'est en ouest, et son entrée se situe tout à l'ouest de la ferme. Dans ce qui suit, l'endroit situé à $k$ mètres à l'est de l'entrée est appelé le point $k$.

Dans la ferme JOI poussent $N$ fraises. Elles sont numérotées de $1$ à $N$. Toutes les fraises sont vertes jusqu'à l'instant $0$. La fraise $i$ ($1 \le i \le N$) pousse au point $A_{i}$ et, à l'instant $T_{i}$, elle mûrit et devient rouge.

Les fraises ne peuvent pas être récoltées tant qu'elles sont vertes. Autrement dit, la fraise $i$ ne peut pas être récoltée avant l'instant $T_{i}$. Vous partez à l'instant $0$ de l'entrée de la ferme située au point $0$, et vous vous déplacez dans la direction est-ouest à une vitesse maximale de $1$ mètre par seconde tout en récoltant les fraises. Le temps nécessaire pour cueillir une fraise est considéré comme négligeable.

Étant donné les informations sur la fraiseraie, écrivez un programme permettant de trouver le temps minimal nécessaire pour récolter toutes les fraises à l'état rouge puis revenir à l'entrée.

Contraintes

• $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$).
• Toutes les valeurs d'entrée sont des entiers.

Entrée

L'entrée est fournie depuis l'entrée standard sous le format suivant :

N
A_1 T_1
A_2 T_2
:
A_N T_N

Sortie

Affichez sur $1$ ligne le temps minimal nécessaire pour récolter toutes les fraises à l'état rouge puis revenir à l'entrée.

Exemple 1

Entrée

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

Sortie

20

Si vous mettez les $10$ premières secondes pour vous rendre au point $10$, vous pouvez récolter en chemin les fraises $2, 4, 5, 7, 8, 9, 10$ dans cet ordre. Ensuite, si vous mettez $10$ secondes pour revenir au point $0$, vous pouvez récolter en chemin les fraises $6, 3, 1$ dans cet ordre. Ainsi, les $10$ fraises peuvent toutes être récoltées à l'état rouge.

Exemple 2

Entrée

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

Sortie

450

En vous déplaçant comme suit, vous pouvez récolter toutes les fraises à l'état rouge en $450$ secondes :

1. Mettre $45$ secondes pour aller jusqu'au point $45$. Comme on est alors à l'instant $45$, on peut récolter la fraise $10$. Après la récolte, mettre $45$ secondes pour revenir au point $0$.
2. Ensuite, mettre $40$ secondes pour aller jusqu'au point $40$. Comme on est alors à l'instant $130$, on peut récolter la fraise $9$. Après la récolte, mettre $40$ secondes pour revenir au point $0$.
3. Ensuite, mettre $35$ secondes pour aller jusqu'au point $35$. Comme on est alors à l'instant $205$, on peut récolter la fraise $8$. Après la récolte, mettre $35$ secondes pour revenir au point $0$.
4. Ensuite, mettre $30$ secondes pour aller jusqu'au point $30$. Comme on est alors à l'instant $270$, on peut récolter la fraise $7$. Après la récolte, mettre $30$ secondes pour revenir au point $0$.
5. Ensuite, mettre $25$ secondes pour aller jusqu'au point $25$. Comme on est alors à l'instant $325$, on peut récolter la fraise $6$. Après la récolte, mettre $25$ secondes pour revenir au point $0$.
6. Ensuite, mettre $20$ secondes pour aller jusqu'au point $20$. Comme on est alors à l'instant $370$, on peut récolter la fraise $5$. Après la récolte, mettre $20$ secondes pour revenir au point $0$.
7. Ensuite, mettre $15$ secondes pour aller jusqu'au point $15$. Comme on est alors à l'instant $405$, on peut récolter la fraise $4$. Après la récolte, mettre $15$ secondes pour revenir au point $0$.
8. Ensuite, mettre $10$ secondes pour aller jusqu'au point $10$. Comme on est alors à l'instant $430$, on peut récolter la fraise $3$. Après la récolte, mettre $10$ secondes pour revenir au point $0$.
9. Ensuite, mettre $5$ secondes pour aller jusqu'au point $5$. Comme on est alors à l'instant $445$, on peut récolter la fraise $2$. Après la récolte, mettre $5$ secondes pour revenir au point $0$.
10. On atteint le point $0$ exactement à l'instant $450$, ce qui permet de récolter la fraise $1$. On arrive au point $0$ au moment même où toutes les fraises sont récoltées.

Exemple 3

Entrée

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

Sortie

198