Ciobănaşul Ion vrea să îşi închidă oile în ţarcuri şi printr-o coincidenţă fericită prietenul lui, Vasile are o firmă de construit ţarcuri. Cum Vasile este bun prieten cu Ion i-a propus să îi construiască ţarcurile gratis, cu condiţia ca ele să aibă un cost cât mai mic. Vasile acceptă să construiască cel mult trei ţarcuri de forma unor pătrate cu laturile paralele cu axele de coordonate. Aceste pătrate trebuie să conţină în interior toate oile, considerând pentru simplitate că o oaie este un punct în plan. Pentru a obţine un cost cât mai mic, trebuie ca latura celui mai mare ţarc să fie cât mai scurtă posibil. Ţarcurile se pot intersecta, iar un punct de pe marginea ţarcului se consideră în interior.
Cerinţă
Ajutaţi-l pe Ion să găsească o soluţie care să îl mulţumească pe Vasile.
Date de intrare
În fişierul de intrare patrate5.in se află pe prima linie un număr natural n ce reprezintă numărul oilor lui Ion, iar pe următoarele n linii poziţiile oilor, adică fiecare astfel de linie conţine două numere întregi x, y separate printr-un singur spaţiu ce reprezintă poziţia unei oi (abscisă şi ordonată).
Date de ieşire
Fişierul de ieşire patrate5.out va conţine un număr natural ce reprezintă latura minimă care o poate avea cel mai mare ţarc dintre cele trei, astfel încât toate oile să fie în interiorul celor trei ţarcuri.
Restricţii
1≤n≤50000
Coordonatele oilor sunt numere întregi din intervalul [0, 50000].
Exemple
patrate5.in
patrate5.out
Explicaţii
5
1 0
2 1
3 2
5 4
6 0
2
Pe figură un patrat are latura de dimensiune zero.
