import java.io.*;
import java.util.*;

public class selva {
    static class Animal implements Comparable<Animal> {
        int id, x, y, u, v;
        public Animal(int id, int x, int y) {
            this.id = id;
            this.x = x;
            this.y = y;
            this.u = x + y;
            this.v = x - y;
        }
        public int compareTo(Animal o) {
            return Integer.compare(this.u, o.u);
        }
    }

    static int[] parent;
    static int find(int i) {
        if (parent[i] == i) return i;
        return parent[i] = find(parent[i]);
    }
    static void unite(int i, int j) {
        int root_i = find(i);
        int root_j = find(j);
        if (root_i != root_j) parent[root_i] = root_j;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int M = sc.nextInt();

        Animal[] animals = new Animal[M];
        for (int i = 0; i < M; i++) {
            animals[i] = new Animal(i, sc.nextInt(), sc.nextInt());
        }
        Arrays.sort(animals);

        int low = 0, high = 2000000000;
        int ans = 0;

        while (low <= high) {
            int mid = low + (high - low) / 2;
            int K = 2 * mid - 1;

            parent = new int[M + 2];
            for (int i = 0; i < M + 2; i++) parent[i] = i;
            int R1 = M, R2 = M + 1;

            for (int i = 0; i < M; i++) {
                if (animals[i].y <= mid - 1 || animals[i].x >= N - mid) unite(animals[i].id, R1);
                if (animals[i].x <= mid - 1 || animals[i].y >= N - mid) unite(animals[i].id, R2);
            }

            TreeSet<int[]> active = new TreeSet<>((a, b) -> {
                if (a[0] != b[0]) return Integer.compare(a[0], b[0]);
                return Integer.compare(a[1], b[1]);
            });

            int left_ptr = 0;
            for (int i = 0; i < M; i++) {
                while (left_ptr < i && animals[i].u - animals[left_ptr].u > K) {
                    active.remove(new int[]{animals[left_ptr].v, animals[left_ptr].id});
                    left_ptr++;
                }

                int[] current = new int[]{animals[i].v, -1};
                int[] ceiling = active.ceiling(current);
                if (ceiling != null && ceiling[0] - animals[i].v <= K) {
                    unite(animals[i].id, ceiling[1]);
                }
                int[] floor = active.floor(current);
                if (floor != null && animals[i].v - floor[0] <= K) {
                    unite(animals[i].id, floor[1]);
                }

                active.add(new int[]{animals[i].v, animals[i].id});
            }

            if (find(R1) == find(R2)) {
                high = mid - 1;
            } else {
                ans = mid;
                low = mid + 1;
            }
        }
        System.out.println(ans);
    }
}