#include <bits/stdc++.h>
using i64 = long long;
#ifdef DEBUG
#include "debug.h"
#else
#define debug(...) void(23)
#endif
constexpr int MAX = int(1E9) + 5;
constexpr int dx[] = {0, +1, 0, -1};
constexpr int dy[] = {+1, 0, -1, 0};
template<typename T>
using min_pq = std::priority_queue<T, std::vector<T>, std::greater<T>>;
template<typename T>
bool chmin(T& a, T b) {
if (a > b) {
a = b;
return true;
}
return false;
}
struct DSU {
std::vector<int> f;
DSU(int n) : f(n) {
std::iota(f.begin(), f.end(), 0);
}
int get(int x) {
while (x != f[x]) {
x = f[x] = f[f[x]];
}
return x;
}
bool unite(int a, int b) {
assert(a == get(a));
a = get(a), b = get(b);
if (a == b) {
return false;
}
f[a] = b;
return true;
}
bool same(int a, int b) {
return get(a) == get(b);
}
};
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);
int N;
std::cin >> N;
std::vector<std::array<int, 2>> A(N);
for (int i = 0; i < N; ++i) {
std::cin >> A[i][0] >> A[i][1];
A[i][0] *= 2;
A[i][1] *= 2;
}
auto meet = [&](int i, int j, int dir) -> std::pair<int, int> {
if (A[i][0] == A[j][0]) {
if (dir == 0 && A[i][1] <= A[j][1]) {
return {2, (A[j][1] - A[i][1]) / 2};
} else if (dir == 2 && A[i][1] >= A[j][1]) {
return {0, (A[i][1] - A[j][1]) / 2};
}
return {-1, -1};
}
if (A[i][1] == A[j][1]) {
if (dir == 1 && A[i][0] <= A[j][0]) {
return {3, (A[j][0] - A[i][0]) / 2};
} else if (dir == 3 && A[i][0] >= A[j][0]) {
return {1, (A[i][0] - A[j][0]) / 2};
}
return {-1, -1};
}
int dis = std::abs(A[i][0] - A[j][0]);
if (A[i][0] + A[i][1] == A[j][0] + A[j][1]) {
if (dir % 2 == 0) {
if (dir == 0 ? A[i][1] <= A[j][1] : A[i][1] >= A[j][1]) {
int ndir = (dir == 0 ? 1 : 3);
return {ndir, dis};
}
return {-1, -1};
} else {
if (dir == 1 ? A[i][0] <= A[j][0] : A[i][0] >= A[j][0]) {
int ndir = (dir == 1 ? 0 : 2);
return {ndir, dis};
}
return {-1, -1};
}
}
if (A[i][0] - A[i][1] == A[j][0] - A[j][1]) {
if (dir % 2 == 0) {
if (dir == 0 ? A[i][1] <= A[j][1] : A[i][1] >= A[j][1]) {
int ndir = (dir == 0 ? 3 : 1);
return {ndir, dis};
}
return {-1, -1};
} else {
if (dir == 1 ? A[i][0] <= A[j][0] : A[i][0] >= A[j][0]) {
int ndir = (dir == 1 ? 2 : 0);
return {ndir, dis};
}
return {-1, -1};
}
}
return {-1, -1};
};
int ans = 0;
auto work = [&]() -> void {
std::vector<std::vector<std::pair<int, int>>> gr(4, std::vector<std::pair<int, int>>(N));
for (int i = 0; i < N; ++i) {
gr[0][i] = std::pair{A[i][0], i};
gr[1][i] = std::pair{A[i][1], i};
gr[2][i] = std::pair{A[i][0] - A[i][1], i};
gr[3][i] = std::pair{A[i][0] + A[i][1], i};
}
std::vector<std::vector<int>> igr(4, std::vector<int>(N));
std::sort(gr[0].begin(), gr[0].end(), [&](auto lhs, auto rhs) {
if (lhs.first != rhs.first) {
return lhs.first < rhs.first;
}
return A[lhs.second][1] < A[rhs.second][1];
});
std::sort(gr[1].begin(), gr[1].end(), [&](auto lhs, auto rhs) {
if (lhs.first != rhs.first) {
return lhs.first < rhs.first;
}
return A[lhs.second][0] < A[rhs.second][0];
});
std::sort(gr[2].begin(), gr[2].end(), [&](auto lhs, auto rhs) {
if (lhs.first != rhs.first) {
return lhs.first < rhs.first;
}
return A[lhs.second][1] < A[rhs.second][1];
});
std::sort(gr[3].begin(), gr[3].end(), [&](auto lhs, auto rhs) {
if (lhs.first != rhs.first) {
return lhs.first < rhs.first;
}
return A[lhs.second][1] < A[rhs.second][1];
});
for (int i = 0; i < 4; ++i) {
for (int j = 0; j < N; ++j) {
igr[i][gr[i][j].second] = j;
}
}
std::vector<DSU> dsus(8, N);
std::vector<std::vector<int>> dir(8, std::vector<int>(N, -1));
std::vector<int> vis(N);
std::vector<std::vector<int>> dis(8, std::vector<int>(N, MAX));
std::vector<min_pq<std::pair<int, int>>> pqs(8);
auto getid = [&](int x, int p) -> int {
if (x / 2 == 0) {
p = gr[0][p].second;
return p;
} else if (x / 2 == 1) {
p = gr[1][p].second;
return p;
} else if (x / 2 == 2) {
p = gr[2][p].second;
return p;
} else if (x / 2 == 3) {
p = gr[3][p].second;
return p;
} else {
assert(false);
return -1;
}
};
auto same = [&](int x, int a, int b) -> bool {
if (x / 2 == 0) {
return A[a][0] == A[b][0];
} else if (x / 2 == 1) {
return A[a][1] == A[b][1];
} else if (x / 2 == 2) {
return A[a][0] - A[a][1] == A[b][0] - A[b][1];
} else if (x / 2 == 3) {
return A[a][0] + A[a][1] == A[b][0] + A[b][1];
} else {
assert(false);
return false;
}
};
auto add = [&](int x, int v, int ds, int dr) -> void {
debug(x, v, ds, dr);
if (dis[x][v] > ds) {
dis[x][v] = ds;
dir[x][v] = dr;
pqs[x].emplace(dis[x][v], v);
}
};
auto add_next = [&](int x, int v) -> void {
if (v == 0) {
return;
}
debug(x, v);
if (x == 0) {
if (igr[0][v] == N - 1) {
return;
}
int z = dsus[0].get(igr[0][v] + 1);
z = getid(0, z);
if (!same(0, v, z)) {
return;
}
int nc = dis[0][v] + (A[z][1] - A[v][1]) / 2;
assert((A[z][0] - A[v][0]) / 2 >= 0);
add(0, z, nc, dir[0][v]);
} else if (x == 1) {
if (igr[0][v] == 0) {
return;
}
int z = dsus[1].get(igr[0][v] - 1);
z = getid(1, z);
if (!same(1, v, z)) {
return;
}
int nc = dis[1][v] + (A[v][1] - A[z][1]) / 2;
assert((A[v][1] - A[z][1]) / 2 >= 0);
add(1, z, nc, dir[1][v]);
} else if (x == 2) {
if (igr[1][v] == N - 1) {
return;
}
int z = dsus[2].get(igr[1][v] + 1);
z = getid(2, z);
if (!same(2, v, z)) {
return;
}
int nc = dis[2][v] + (A[z][0] - A[v][0]) / 2;
assert((A[z][0] - A[v][0]) / 2 >= 0);
add(2, z, nc, dir[2][v]);
} else if (x == 3) {
if (igr[1][v] == 0) {
return;
}
int z = dsus[3].get(igr[1][v] - 1);
z = getid(3, z);
if (!same(3, v, z)) {
return;
}
int nc = dis[3][v] + (A[v][0] - A[z][0]) / 2;
assert((A[v][0] - A[z][0]) / 2 >= 0);
add(3, z, nc, dir[3][v]);
} else if (x == 4) {
if (igr[2][v] == N - 1) {
return;
}
int z = dsus[4].get(igr[2][v] + 1);
z = getid(4, z);
if (!same(4, v, z)) {
return;
}
int nc = dis[4][v] + (A[z][0] - A[v][0]);
assert((A[z][0] - A[v][0]) >= 0);
add(4, z, nc, dir[4][v]);
} else if (x == 5) {
if (igr[2][v] == 0) {
return;
}
int z = dsus[5].get(igr[2][v] - 1);
z = getid(5, z);
if (!same(5, v, z)) {
return;
}
int nc = dis[5][v] + (A[v][1] - A[z][1]);
assert((A[v][1] - A[z][1]) >= 0);
add(5, z, nc, dir[5][v]);
} else if (x == 6) {
if (igr[3][v] == N - 1) {
return;
}
int z = dsus[6].get(igr[3][v] + 1);
z = getid(6, z);
if (!same(6, v, z)) {
return;
}
int nc = dis[6][v] + (A[z][1] - A[v][1]);
assert((A[z][1] - A[v][1]) >= 0);
add(6, z, nc, dir[6][v]);
} else if (x == 7) {
if (igr[3][v] == 0) {
return;
}
int z = dsus[7].get(igr[3][v] - 1);
z = getid(7, z);
if (!same(7, v, z)) {
return;
}
int nc = dis[7][v] + (A[v][1] - A[z][1]);
assert((A[v][1] - A[z][1]) >= 0);
add(7, z, nc, dir[7][v]);
} else {
assert(false);
}
};
auto jump_nexts = [&](int v, int ds, int dr) -> void {
debug("jump nexts", v, ds, dr);
for (int i = 0; i < 8; ++i) {
if (i % 2 == 0) {
int p = igr[i / 2][v];
if (p != N - 1) {
dsus[i].unite(p, p + 1);
}
} else {
int p = igr[i / 2][v];
if (p != 0) {
dsus[i].unite(p, p - 1);
}
}
}
if (dr == 0) {
// 0, v, ds, 2
{
int p = dsus[0].get(igr[0][v]);
for (int i = 17; i >= -1; --i) {
int k = i >= 0 ? (1 << i) : 1;
auto[met1, met2] = meet(v, getid(0, p), dr);
if (met1 == -1 || met2 < ds) {
if (p + k < N) {
int nxt = dsus[0].get(p + k);
auto[net1, net2] = meet(v, getid(0, nxt), dr);
if (same(0, v, getid(0, nxt))) {
if (i == -1 || (net1 == -1 || net2 < ds)) {
p = nxt;
}
}
}
}
}
if (same(0, v, getid(0, p))) {
auto[met1, met2] = meet(v, getid(0, p), dr);
if (met2 >= ds) {
add(0, getid(0, p), met2, 2);
}
}
}
// 4, v, ds, 3
{
int p = dsus[4].get(igr[2][v]);
for (int i = 17; i >= -1; --i) {
int k = i >= 0 ? (1 << i) : 1;
auto[met1, met2] = meet(v, getid(4, p), dr);
if (met1 == -1 || met2 < ds) {
if (p + k < N) {
int nxt = dsus[4].get(p + k);
auto[net1, net2] = meet(v, getid(4, nxt), dr);
if (same(4, v, getid(4, nxt))) {
if (i == -1 || (net1 == -1 || net2 < ds)) {
p = nxt;
}
}
}
}
}
if (same(4, v, getid(4, p))) {
auto[met1, met2] = meet(v, getid(4, p), dr);
if (met2 >= ds) {
add(4, getid(4, p), met2, 3);
}
}
}
// 6, v, ds, 1
{
int p = dsus[6].get(igr[3][v]);
for (int i = 17; i >= -1; --i) {
int k = i >= 0 ? (1 << i) : 1;
auto[met1, met2] = meet(v, getid(6, p), dr);
if (met1 == -1 || met2 < ds) {
if (p + k < N) {
int nxt = dsus[6].get(p + k);
auto[net1, net2] = meet(v, getid(6, nxt), dr);
if (same(6, v, getid(6, nxt))) {
if (i == -1 || (net1 == -1 || net2 < ds)) {
p = nxt;
}
}
}
}
}
if (same(6, v, getid(6, p))) {
auto[met1, met2] = meet(v, getid(6, p), dr);
if (met2 >= ds) {
add(6, getid(6, p), met2, 1);
}
}
}
} else if (dr == 1) {
// 4, v, ds, 2
{
int p = dsus[4].get(igr[2][v]);
for (int i = 17; i >= -1; --i) {
int k = i >= 0 ? (1 << i) : 1;
auto[met1, met2] = meet(v, getid(4, p), dr);
if (met1 == -1 || met2 < ds) {
if (p + k < N) {
int nxt = dsus[4].get(p + k);
auto[net1, net2] = meet(v, getid(4, nxt), dr);
if (same(4, v, getid(4, nxt))) {
if (i == -1 || (net1 == -1 || net2 < ds)) {
p = nxt;
}
}
}
}
}
if (same(4, v, getid(4, p))) {
auto[met1, met2] = meet(v, getid(4, p), dr);
if (met2 >= ds) {
add(4, getid(4, p), met2, 2);
}
}
}
// 2, v, ds, 3
{
int p = dsus[2].get(igr[1][v]);
for (int i = 17; i >= -1; --i) {
int k = i >= 0 ? (1 << i) : 1;
auto[met1, met2] = meet(v, getid(2, p), dr);
if (met1 == -1 || met2 < ds) {
if (p + k < N) {
int nxt = dsus[2].get(p + k);
auto[net1, net2] = meet(v, getid(2, nxt), dr);
if (same(2, v, getid(2, nxt))) {
if (i == -1 || (net1 == -1 || net2 < ds)) {
p = nxt;
}
}
}
}
}
if (same(2, v, getid(2, p))) {
auto[met1, met2] = meet(v, getid(2, p), dr);
if (met2 >= ds) {
add(2, getid(2, p), met2, 3);
}
}
}
// 7, v, ds, 0
{
int p = dsus[7].get(igr[3][v]);
for (int i = 17; i >= -1; --i) {
int k = i >= 0 ? -(1 << i) : -1;
auto[met1, met2] = meet(v, getid(7, p), dr);
if (met1 == -1 || met2 < ds) {
if (p + k >= 0) {
int nxt = dsus[7].get(p + k);
auto[net1, net2] = meet(v, getid(7, nxt), dr);
if (same(7, v, getid(7, nxt))) {
if (i == -1 || (net1 == -1 || net2 < ds)) {
p = nxt;
}
}
}
}
}
if (same(7, v, getid(7, p))) {
auto[met1, met2] = meet(v, getid(7, p), dr);
if (met2 >= ds) {
add(7, getid(7, p), met2, 0);
}
}
}
} else if (dr == 2) {
// 7, v, ds, 3
{
int p = dsus[7].get(igr[3][v]);
for (int i = 17; i >= -1; --i) {
int k = i >= 0 ? -(1 << i) : -1;
auto[met1, met2] = meet(v, getid(7, p), dr);
if (met1 == -1 || met2 < ds) {
if (p + k >= 0) {
int nxt = dsus[7].get(p + k);
auto[net1, net2] = meet(v, getid(7, nxt), dr);
if (same(7, v, getid(7, nxt))) {
if (i == -1 || (net1 == -1 || net2 < ds)) {
p = nxt;
}
}
}
}
}
if (same(7, v, getid(7, p))) {
auto[met1, met2] = meet(v, getid(7, p), dr);
if (met2 >= ds) {
add(7, getid(7, p), met2, 3);
}
}
}
// 1, v, ds, 0
{
int p = dsus[1].get(igr[0][v]);
for (int i = 17; i >= -1; --i) {
int k = i >= 0 ? -(1 << i) : -1;
auto[met1, met2] = meet(v, getid(1, p), dr);
if (met1 == -1 || met2 < ds) {
if (p + k >= 0) {
int nxt = dsus[1].get(p + k);
auto[net1, net2] = meet(v, getid(1, nxt), dr);
if (same(1, v, getid(1, nxt))) {
if (i == -1 || (net1 == -1 || net2 < ds)) {
p = nxt;
}
}
}
}
}
if (same(1, v, getid(1, p))) {
auto[met1, met2] = meet(v, getid(1, p), dr);
if (met2 >= ds) {
add(1, getid(1, p), met2, 0);
}
}
}
// 5, v, ds, 1
{
int p = dsus[5].get(igr[2][v]);
for (int i = 17; i >= -1; --i) {
int k = i >= 0 ? -(1 << i) : -1;
auto[met1, met2] = meet(v, getid(5, p), dr);
if (met1 == -1 || met2 < ds) {
if (p + k >= 0) {
int nxt = dsus[5].get(p + k);
auto[net1, net2] = meet(v, getid(5, nxt), dr);
if (same(5, v, getid(5, nxt))) {
if (i == -1 || (net1 == -1 || net2 < ds)) {
p = nxt;
}
}
}
}
}
if (same(5, v, getid(5, p))) {
auto[met1, met2] = meet(v, getid(5, p), dr);
if (met2 >= ds) {
add(5, getid(5, p), met2, 1);
}
}
}
} else if (dr == 3) {
// 5, v, ds, 0
{
int p = dsus[5].get(igr[2][v]);
for (int i = 17; i >= -1; --i) {
int k = i >= 0 ? -(1 << i) : -1;
auto[met1, met2] = meet(v, getid(5, p), dr);
if (met1 == -1 || met2 < ds) {
if (p + k >= 0) {
int nxt = dsus[5].get(p + k);
auto[net1, net2] = meet(v, getid(5, nxt), dr);
if (same(5, v, getid(5, nxt))) {
if (i == -1 || (net1 == -1 || net2 < ds)) {
p = nxt;
}
}
}
}
}
if (same(5, v, getid(5, p))) {
auto[met1, met2] = meet(v, getid(5, p), dr);
if (met2 >= ds) {
add(5, getid(5, p), met2, 0);
}
}
}
// 3, v, ds, 1
{
int p = dsus[3].get(igr[1][v]);
for (int i = 17; i >= -1; --i) {
int k = i >= 0 ? -(1 << i) : -1;
auto[met1, met2] = meet(v, getid(3, p), dr);
if (met1 == -1 || met2 < ds) {
if (p + k >= 0) {
int nxt = dsus[3].get(p + k);
auto[net1, net2] = meet(v, getid(3, nxt), dr);
if (same(3, v, getid(3, nxt))) {
if (i == -1 || (net1 == -1 || net2 < ds)) {
p = nxt;
}
}
}
}
}
if (same(3, v, getid(3, p))) {
auto[met1, met2] = meet(v, getid(3, p), dr);
if (met2 >= ds) {
add(3, getid(3, p), met2, 1);
}
}
}
// 6, v, ds, 2
{
int p = dsus[6].get(igr[3][v]);
for (int i = 17; i >= -1; --i) {
int k = i >= 0 ? (1 << i) : 1;
auto[met1, met2] = meet(v, getid(6, p), dr);
if (met1 == -1 || met2 < ds) {
if (p + k < N) {
int nxt = dsus[6].get(p + k);
auto[net1, net2] = meet(v, getid(6, nxt), dr);
if (same(6, v, getid(6, nxt))) {
if (i == -1 || (net1 == -1 || net2 < ds)) {
p = nxt;
}
}
}
}
}
if (same(6, v, getid(6, p))) {
auto[met1, met2] = meet(v, getid(6, p), dr);
if (met2 >= ds) {
add(6, getid(6, p), met2, 2);
}
}
}
} else {
assert(false);
}
};
add(0, 0, 0, 0);
while (true) {
std::pair<int, int> x = {MAX, -1};
for (int i = 0; i < 8; ++i) {
while (!pqs[i].empty() && vis[pqs[i].top().second]) {
add_next(i, pqs[i].top().second);
pqs[i].pop();
}
if (!pqs[i].empty()) {
x = std::min(x, pqs[i].top());
}
}
if (x.second == -1) {
break;
}
for (int i = 0; i < 8; ++i) {
if (!pqs[i].empty() && pqs[i].top() == x) {
pqs[i].pop();
int v = x.second;
add_next(i, v);
vis[v] = true;
debug(v, dis[i][v], dir[i][v], A[v]);
jump_nexts(v, dis[i][v], dir[i][v]);
break;
}
}
}
debug(vis);
ans = std::max(ans, std::accumulate(vis.begin(), vis.end(), 0));
};
for (int i = 0; i < 4; ++i) {
for (int j = 0; j < N; ++j) {
debug(j, A[j]);
}
work();
for (int j = 0; j < N; ++j) {
std::tie(A[j][0], A[j][1]) = std::make_pair(-A[j][1], A[j][0]);
}
debug();
}
std::cout << ans << '\n';
return 0;
};
