Omida2

Ce-s încă șaptișpe ani între prieteni?

Cerință

Într-un tărâm îndepărtat, pe care îl vom descrie printr-un sistem cartezian de coordonate xOy, trăiește un arcaș. Sarcina lui este să nimerească toate cele $N$ ținte din patria sa. Casa arcașului se află la coordonata $(0, 0)$, loc de unde va începe aventura sa.

El se poate deplasa în oricare dintre punctele adiacente pe baza punctelor cardinale (nord, sud, est și vest), adică din punctul $(X, Y)$, arcașul se poate muta către oricare dintre $(X + 1, Y)$, $(X - 1, Y)$, $(X, Y + 1)$, $(X, Y - 1)$. O astfel de mișcare durează o secundă.

Din orice punct $(X, Y)$, arcașul poate trage în orice direcție nord-est și sud-vest. După lansarea unei săgeți, aceasta își va păstra direcția pe tot parcursul traiectoriei sale (adică nu se schimbă niciodată de la nord-est la sud-vest sau invers). Lansarea unei săgeți este instantanee, adică durează $0$ secunde, și fiecare săgeată lansată își va începe mișcarea de la aceeași coordonată la care se află arcașul în momentul tragerii. Pentru orice săgeată ce se află la coordonata $(X, Y)$, dacă aceasta călătorește în direcția nord-est, după o secundă săgeata se va afla la coordonata $(X + 1, Y + 1)$. Similar, pentru o săgeată aflată la o coordonată $(X, Y)$, care călătorește în direcția sud-vest, după o secundă săgeata se va afla la coordonata $(X - 1, Y - 1)$.

Cu ajutorul acestor săgeți, arcașul va lovi toate cele $N$ ținte. În orice moment, dacă o săgeată și o țintă se află la aceeași coordonată, ele pot fie să dispară amândouă (se anihilează fără niciun efect asupra oricărei alte săgeți sau ținte), fie săgeata respectivă poate continua pe traiectoria sa, ignorând ținta.

Raportați timpul minim $T$ la care, după o secvență optimă de mișcări efectuate de arcaș, toate țintele dispar din plan.

Date de intrare

Pe prima linie, se va afla $N$ - numărul de ținte.

Urmeaza $N$ linii; pe a $i$-a linie se află câte două numere, $X_{i}$ și $Y_{i}$ - coordonatele celei de-a $i$-a ținte.

Date de ieșire

Afișați timpul minim $T$ la care, după o secvență optimă de mișcări efectuate de arcaș, toate țintele dispar din plan.

Restricții și precizări

• $N \leq 100\,000$;
• $-1\ 000\ 000 \leq X_i, Y_i \leq 1\ 000\ 000$ pentru oricare $1 \leq i \leq N$;
• Atenție! $X_{i} \geq Y_{i}$ pentru oricare $1 \leq i \leq N$.

Subtask-uri

Exemplul 1

stdin

8
15 13
0 -3
-3 -7
19 17
-3 -7
5 0
11 6
8 4

stdout

19

Exemplul 2

stdin

20
100 72
-44 -48
94 49
48 16
10 -21
100 55
-30 -45
-8 -49
-21 -72
-57 -87
64 27
40 -5
-38 -88
49 6
-37 -69
23 5
99 50
94 63
-68 -98
-42 -93

stdout

121

Exemplul 3

stdin

10
28 4
34 8
18 13
22 12
33 0
26 8
13 11
35 1
33 3
27 25

stdout

35