#include <bits/stdc++.h>

using namespace std;

class unionfind {
	vector<int> rep, sz;

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

public:
	unionfind(int n) : rep (n), sz (n, 1) {
		iota(rep.begin(), rep.end(), 0);
	}

	void une(int u, int v) {
		u = find(u); v = find(v);

		if (u == v) return;

		if (sz[u] < sz[v]) swap(u, v);
		rep[v] = u; sz[u] += sz[v];
	}

	bool same(int u, int v) { return find(u) == find(v); }
};

bool check(const vector<pair<int, int>> &P, int d, int n) {
	int delta = 2*d - 1;
	
	unionfind U(P.size() + 2);
	int left_border = P.size(), right_border = P.size() + 1;

	for (int i = 0; i < P.size(); ++i) {
		auto [p, q] = P[i];
		int x = (p + q)/2, y = (p - q)/2;

		if (x < d || y >= n - d) U.une(i, left_border);
		if (x >= n - d || y < d) U.une(i, right_border);
	}

	set<pair<int, int>> qs;
	for (int i = 0, j = 0; i < P.size(); ++i) {
		for (; j < P.size() && P[j].first < P[i].first - delta; ++j) 
			qs.erase({P[j].second, j});
		
		auto it = qs.lower_bound({P[i].second, 0});
		if (it != qs.end() && it->first <= P[i].second + delta)
			U.une(it->second, i);

		if (it != qs.begin() && prev(it)->first >= P[i].second - delta)
			U.une(prev(it)->second, i);

		qs.emplace(P[i].second, i);
	}

	return !U.same(left_border, right_border);
}

int main() {
	int n, m;
	cin >> n >> m;

	vector<pair<int, int>> P(m);
	for (auto &[p, q]: P) {
		int x, y;
		cin >> x >> y;

		p = x + y; q = x - y;
	}

	sort(P.begin(), P.end());

	int l = 0, r = 1e9;
	while (l < r) {
		int m = (l + r) >> 1;
		if (check(P, m, n)) l = m + 1;
		else r = m;
	}

	cout << l - 1 << "\n";
}