#include<bits/stdc++.h>
#define F first
#define S second
#define pb push_back
#define all(x) x.begin(), x.end()
#define debug(x) cerr << #x << " : " << x << '\n'
// #define int long long
using namespace std;
typedef pair<int, int> pii;
const int N = 1e5 + 10;
const int Inf = 1'000'000'010;
int n;
int x[N], y[N];
int dir[N];
pii vec[] = {{1, 0}, {0, -1}, {-1, 0}, {0, 1}};
set< pair<int, int> > st; // time, id
int mk[N];
set<pair<int, int> > vis;
int Collision(int a, int b){
if(x[a] > x[b]) swap(a, b);
if(x[a] == x[b]){
if(y[a] > y[b]) swap(a, b);
if(dir[a] == 3 && dir[b] == 1)
return abs(y[a] - y[b]) / 2;
return Inf;
}
if(y[a] == y[b]){
// if(y[a] > y[b]) swap(a, b);
if(dir[a] == 0 && dir[b] == 2)
return abs(x[a] - x[b]) / 2;
return Inf;
}
int dp_a = x[a] + y[a];
int dp_b = x[b] + y[b];
int dn_a = x[a] - y[a];
int dn_b = x[b] - y[b];
if(dp_a != dp_b && dn_a != dn_b)
return Inf;
int d = abs(x[a] - x[b]);
if(dp_a == dp_b){
if((dir[a] == 0 && dir[b] == 3) || (dir[a] == 1 && dir[b] == 2))
return d;
return Inf;
}
if((dir[a] == 0 && dir[b] == 1) || (dir[a] == 3 && dir[b] == 2))
return d;
return Inf;
}
int dis[N];
struct Line {
int spd = 1, sz;
vector<pii> Stop, Move;
vector<pii> ans, mn;
vector<int> lz;
void Apply(int id, int x){
// debug(x);
ans[id] = min(ans[id], pii(mn[id].F + x, mn[id].S));
lz[id] = min(lz[id], x);
}
void Shift(int id){
if(lz[id] != 1){
Apply(id << 1, lz[id]);
Apply(id << 1 | 1, lz[id]);
}
lz[id] = 1;
}
void Build(int id, int L, int R){
lz[id] = 1;
if(L + 1 == R){
ans[id] = {Inf, Stop[L].S};
mn[id] = Stop[L];
return ;
}
int mid = (L + R) >> 1;
Build(id << 1, L, mid);
Build(id<<1|1, mid, R);
ans[id]=min(ans[id << 1], ans[id << 1 | 1]);
mn[id] = min(mn[id << 1], mn[id << 1 | 1]);
}
void Off(int id, int idx, int L, int R){
if(L + 1 == R){
mn[id].F = Inf + Inf;
ans[id] = mn[id];
return ;
}
int mid = (L + R) >> 1;
Shift(id);
if(idx < mid)
Off(id << 1, idx, L, mid);
else
Off(id<<1|1, idx, mid, R);
ans[id] = min(ans[id << 1], ans[id << 1 | 1]);
mn[id] = min(mn[id << 1], mn[id << 1 | 1]);
}
void Add(int id, int l, int r, int x, int L, int R){
// for(int i = l; i < r; i++)
// return ;
if(r <= L || R <= l) return ;
if(l <= L && R <= r){
Apply(id, x);
return ;
}
int mid = (L + R) >> 1;
Shift(id);
Add(id << 1, l, r, x, L, mid);
Add(id<<1|1, l, r, x, mid, R);
ans[id] = min(ans[id << 1], ans[id << 1 | 1]);
mn[id] = min(mn[id << 1], mn[id << 1 | 1]);
}
void Add_Stop(int pos, int id){
Stop.pb({pos, id});
}
void Add_Move(int pos, int id){
Move.pb({pos, id});
}
void Init(){
sz = Stop.size();
if(Stop.empty())
return ;
for(auto &el : Stop)
el.F /= spd;
for(auto &el : Move)
el.F /= spd;
sort(all(Stop));
ans.resize(sz * 4);
mn.resize(sz * 4);
lz.resize(sz * 4);
Build(1, 0, sz);
}
void Infect_Move(int pos, int id, int tm){
// debug(id);
// debug(tm);
pos /= spd;
// int dbg = 0;
// if(dbg){
// for(auto el : Stop){
// int i = el.S;
// // cerr << "&& " << id << ' ' << i << '\n';
// if(el.F < pos + tm) continue;
// if(mk[i]) continue;
// int ds = Collision(id, i);
// assert(ds == el.F - pos);
// if(dis[i] > ds){
// st.erase({dis[i], i});
// dis[i] = ds;
// st.insert({ds, i});
// }
// }
// }
// for(auto [_pos, _id] : Stop){
// if(mk[_id]) continue;
// if(pos + tm <= _pos && !mk[_id]){
// assert(Collision(id, _id) == _pos - pos);
// if(dis[_id] > _pos - pos){
// st.erase({dis[_id], _id});
// dis[_id] = _pos - pos;
// st.insert({dis[_id], _id});
// }
// }
// }
int idx = lower_bound(all(Stop), pii(pos + tm, -1)) - Stop.begin();
if(idx == sz)
return ;
// debug(pos);
Add(1, idx, sz, -pos, 0, sz);
if(dis[ans[1].S] > ans[1].F){
st.erase({dis[ans[1].S], ans[1].S});
dis[ans[1].S] = ans[1].F;
st.insert(ans[1]);
}
}
void Infect_Stop(int pos, int id, int tm){
pos /= spd;
int idx = lower_bound(all(Stop), pii(pos, id)) - Stop.begin();
// assert(idx < sz);
assert(Stop[idx] == pii(pos, id));
Off(1, idx, 0, sz);
if(dis[ans[1].S] > ans[1].F){
st.erase({dis[ans[1].S], ans[1].S});
dis[ans[1].S] = ans[1].F;
st.insert(ans[1]);
}
}
void Reset(){
Stop.clear();
Move.clear();
}
};
Line DIA[4][4][N], U[N], R[N];
int CP[N], CN[N], CXX[N], CYY[N];
int rv[4][4], ty[4][4];
void Infect(int u, int tm){
assert(mk[u] == 0);
mk[u] = 1;
// for(int i = 0; i < n; i++){
// if(mk[i]) continue;
// int ds = Collision(u, i);
// if(ds != Inf)
// vis.insert({u, i});
// if(ds >= tm && ds != Inf && dis[i] > ds){
// st.erase({dis[i], i});
// dis[i] = ds;
// st.insert({ds, i});
// }
// }
// return ;
// debug(u);
int MAX = 1'000'000'000;
int pos;
for(int d2 = 0; d2 < 4; d2 ++){
if((dir[u] + d2) % 2 == 0) continue;
pos = rv[dir[u]][d2] ? MAX - x[u] : x[u];
DIA[dir[u]][d2][ ty[dir[u]][d2] ? CN[u] : CP[u]].Infect_Move(pos, u, tm);
pos = rv[d2][dir[u]] ? MAX - x[u] : x[u];
DIA[d2][dir[u]][ ty[d2][dir[u]] ? CN[u] : CP[u]].Infect_Stop(pos, u, tm);
}
int imp = dir[u] & 1 ? y[u] : x[u];
pos = rv[dir[u]][dir[u] ^ 2] ? MAX - imp : imp;
DIA[dir[u]][dir[u] ^ 2][dir[u] & 1 ? CXX[u] : CYY[u]].Infect_Move(pos, u, tm);
pos = rv[dir[u] ^ 2][dir[u]] ? MAX - imp : imp;
DIA[dir[u] ^ 2][dir[u]][dir[u] & 1 ? CXX[u] : CYY[u]].Infect_Stop(pos, u, tm);
}
int Solve(){
dir[0] = 0;
for(int i = 1; i < n; i++){
int X = abs(x[i] - x[0]);
int Y = abs(y[i] - y[0]);
if(X == Y){
if(x[i] < x[0]) dir[i] = 0;
else dir[i] = y[i] < y[0] ? 3 : 1;
} else {
if(X > Y){
if( x[i] < x[0]) dir[i] = 0;
else dir[i] = 2;
} else {
if( y[i] < y[0]) dir[i] = 3;
else dir[i] = 1;
}
}
}
// cerr << "!! " ;
// for(int i = 0; i < n; i++){
// cerr << dir[i] << ' ';
// }
// cerr << '\n';
// cerr << "!! " << x[0] << ' ' << y[0] << ' ' << x[1] << ' ' << y[1] << '\n';
// for(int i = 0; i < N; i++) R[i].Reset(), U[i].Reset();
for(int i = 0; i < 16; i++)
for(int j = 0; j < N; j++)
DIA[i >> 2][i & 3][j].Reset();
for(int i = 0; i < 4; i++)
for(int j = 0; j < N; j++)
DIA[i][i ^ 2][j].spd = 2;
int MAX = 1'000'000'000;
for(int i = 0; i < n; i++){
int pos;
for(int d2 = 0; d2 < 4; d2 ++){
if((dir[i] + d2) % 2 == 0) continue;
pos = rv[dir[i]][d2] ? MAX - x[i] : x[i];
DIA[dir[i]][d2][ ty[dir[i]][d2] ? CN[i] : CP[i]].Add_Move(pos, i);
pos = rv[d2][dir[i]] ? MAX - x[i] : x[i];
DIA[d2][dir[i]][ ty[d2][dir[i]] ? CN[i] : CP[i]].Add_Stop(pos, i);
}
int imp = dir[i] & 1 ? y[i] : x[i];
pos = rv[dir[i]][dir[i] ^ 2] ? MAX - imp : imp;
DIA[dir[i]][dir[i] ^ 2][dir[i] & 1 ? CXX[i] : CYY[i]].Add_Move(pos, i);
pos = rv[dir[i] ^ 2][dir[i]] ? MAX - imp : imp;
DIA[dir[i] ^ 2][dir[i]][dir[i] & 1 ? CXX[i] : CYY[i]].Add_Stop(pos, i);
}
for(int i = 0; i < 16; i++)
for(int j = 0; j < N; j++)
DIA[i >> 2][i & 3][j].Init();
memset(mk, 0, sizeof mk);
fill(dis, dis + N, Inf);
dis[0] = 0;
st.insert({0, 0});
while(!st.empty()){
// cerr << "&&&&&&&\n";
// for(auto [a1, a2] : st)
// cerr << a1 << ' ' << a2 << '\n';
// cerr << "-------\n";
int fr = st.begin() -> S;
int tm = st.begin() -> F;
st.erase(st.begin());
// if(tm > Inf) continue;
// cerr << "!! " << fr << ' ' << tm << '\n';
Infect(fr, tm);
}
int res = 0;
for(int i = 0; i < n; i++)
res += mk[i];
return res;
}
int32_t main(){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
rv[3][0] = 1; rv[1][0] = 1;
rv[2][1] = 1; rv[2][3] = 1;
rv[2][0] = 1; rv[1][3] = 1;
ty[0][1] = ty[1][0] = ty[2][3] = ty[3][2] = 1;
cin >> n;
vector<int> cp, cn, cxx, cyy;
for(int i = 0; i < n; i++){
cin >> x[i] >> y[i];
cp.pb(x[i] + y[i]);
cn.pb(x[i] - y[i]);
cxx.pb(x[i]);
cyy.pb(y[i]);
}
sort(all(cp));
sort(all(cn));
sort(all(cxx));
sort(all(cyy));
for(int i = 0; i < n; i++)
CP[i] = lower_bound(all(cp), x[i] + y[i]) - cp.begin();
for(int i = 0; i < n; i++)
CN[i] = lower_bound(all(cn), x[i] - y[i]) - cn.begin();
for(int i = 0; i < n; i++)
CXX[i] = lower_bound(all(cxx), x[i]) - cxx.begin();
for(int i = 0; i < n; i++)
CYY[i] = lower_bound(all(cyy), y[i]) - cyy.begin();
for(int i = 0; i < n; i++){
x[i] += x[i];
y[i] += y[i];
}
int ans = 0;
int MAX = 1'000'000'000;
for(int _ = 0; _ < 4; _++){
ans = max(ans, Solve());
for(int i = 0; i < n; i++){
int _x = x[i];
x[i] = MAX-y[i];
y[i] = _x;
}
for(int i = 0; i < n; i++)
swap(CP[i], CN[i]);
for(int i = 0; i < n; i++)
swap(CXX[i], CYY[i]);
// break;
}
cout << ans << '\n';
// for(auto [a1, a2] : vis)
// cerr << "! " << a1 << ' ' << a2 << '\n';
return 0;
}
