Klasický staroveký poľnohospodár v Ríme vymyslel revolučný spôsob zbavovania sa buriny. Namiesto nekonečného vytrhávania si zobral tmavú tkaninu a burinu jednoducho prikryl. Však keď nebude mať svetlo, vykape. Ako vznešený obyvateľ impéria má však farmár vycibrený zmysel pre estetiku a geometriu. Zásadne preto používa len dokonalé štvorcové kusy látky. Pri plánovaní prišiel na zaujímavý logistický ťah: vypočítal si, že ak jednu strategicky zvolenú burinu nechá tak (nezakryje ju), rozmery potrebného štvorca sa výrazne zmenšia, čím ušetrí drahocenný materiál. Pole je však veľké a buriny veľa, preto sa obracia s prosbou o pomoc na Teba!

Úloha

Máme n bodov v rovine. Nájdi dĺžku strany najmenšieho štvorca, ktorým vieme pokryť všetky dané body okrem jedného. Štvorec musí mať strany rovnobežné s osami x a y.

Formát vstupu

V prvom riadku vstupu je číslo $n$ udávajúce počet bodov. Nasleduje $n$ riadkov, pričom na každom riadku sú dve medzerou oddelené čísla, x-ová súradnica bodu a y-ová súradnica bodu.

V jednotlivých sadách platia nasledujúce obmedzenia:

Formát výstupu

Vypíš jeden riadok a v ňom jedno číslo, veľkosť strany najmenšieho štvorca.

Príklad

5
0 0
1 3
3 1
4 4
6 2

4

Keď sa rozhodneme nezakryť bod zo súradnicami (6,2), zvyšné body budeme vedieť zakryť štvorcom zo stranou 4.

7
2 7
0 5
6 7
3 3
6 2
0 0
4 0

7

Nech sa rozhodneme vynechať ktorýkoľvek bod, veľkosť potrebného štvorca sa nezmení, vždy budeme potrebovať štvorec so stranou dĺžky 7.