#include <bits/stdc++.h>
using namespace std; 

#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define FOR(i, a, b) for( int i = a; i < (b); i++ )

using vi = vector<int>; 
using ll = long long;
using pii = pair<int, int>; 

const ll inf = 1e18; 

struct Point{
    ll x, y, u, v; int id; 
    bool operator < ( const Point &o ) const {
        return tie(v, id) < tie(o.v, o.id); 
    }
    ll dist( const Point &o ) const {
        return abs(x - o.x) + abs(y - o.y); 
    }
};

struct Event{
    ll u, id, type; 
    bool operator < ( const Event &o ) const {
        return tie(u, type) < tie(o.u, o.type); 
    }
};

struct DSU{
    vi par, siz; 
    DSU(int n) : par(n), siz(n, 1){
        iota(all(par), 0); 
    }

    int find( int u ){
        return ((u == par[u]) ? u : par[u] = find(par[u])); 
    }

    void join( int u, int v ){
        u = find(u), v = find(v); 
        if( u == v ) return; 
        if( siz[u] < siz[v] ) swap( u, v ); 
        par[v] = u; 
        siz[u] += siz[v]; 
    }
};

bool check( ll r, int n, vector<Point> &animals ){
    int m = sz(animals);
    int upper = m, lower = m + 1; 
    DSU dsu(m + 2); 

    for( auto [x, y, u, v, id] : animals ){
        if( x - r < 0 || y + r >= n ) dsu.join(id, upper); 
        if( x + r >= n || y - r < 0 ) dsu.join(id, lower); 
    }

    set<Point> active; 
    active.insert({ 0, 0, 0, -inf, -1 }); 
    active.insert({ 0, 0, 0, inf,  -1 });

    int p = 0; 
    for( auto animal : animals ){
        ll u = animal.u, v = animal.v; 
        int id = animal.id;  
        while( p < m && animals[p].u <= u - 2*r ) active.erase(animals[p++]);
        Point p1 = *active.lower_bound(Point{ 0, 0, 0, v - 2*r + 1, -1 }); 
        Point p2 = *prev(active.upper_bound(Point{ 0, 0, 0, v + 2*r - 1, m }));

        if( p1.id != -1 && p1.dist(animal) < 2*r ) dsu.join(id, p1.id); 
        if( p2.id != -1 && p2.dist(animal) < 2*r ) dsu.join(id, p2.id); 

        active.insert(animal);
    }

    return dsu.find(upper) != dsu.find(lower); 
}

int bs( int n, vector<Point> &animals ){
    ll l = 0, r = 2*n; 
    while( l < r ){
        ll m = (l + r + 1)/2; 
        if( check( m, n, animals ) ) l = m; 
        else r = m - 1; 
    }
    return l; 
}

void solve(){
    int n, m; cin >> n >> m; 
    vector<Point> animals; 
    FOR(i, 0, m){
        int x, y; cin >> x >> y; 
        animals.push_back({ x, y, x + y, x - y, -1 }); 
    }
    sort(all(animals), [&]( Point a, Point b ){
        return a.u < b.u; 
    });
    FOR(i, 0, m) animals[i].id = i; 

    cout << bs(n, animals) << '\n';
}

int main(){
    ios::sync_with_stdio(false); cin.tie(NULL); 
    solve(); 
}