rt

// # pragma GCC optimize("Ofast,no-stack-protector")
//
// # pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

# include <bits/stdc++.h>

using namespace std;

typedef long long ll;

typedef pair <int, int> pii;

typedef int arr[1005][1005];

int n, m, t, maxx, x, y;

arr l, r, L, R, u;

char c;

bitset <1005> a[1005];

int main () {

	ios::sync_with_stdio (0);

	cin.tie (0);

	cout.tie (0);

	cin >> n >> m;

    while (m --)
        cin >> x >> y, a[x][y] = 1;

	for (int i = 1; i <= n; ++ i) {

		for (int j = 1; j <= n; ++ j)
			if (! a[i][j]) {

				l[i][j] = l[i][j - 1] + 1;

				u[i][j] = u[i - 1][j] + 1;

				if (a[i - 1][j])
					L[i][j] = l[i][j];
				else
					L[i][j] = min (L[i - 1][j], l[i][j]);

			}

		for (int j = n; j; -- j)
			if (! a[i][j]) {

				r[i][j] = r[i][j + 1] + 1;

				if (a[i - 1][j])
					R[i][j] = r[i][j];
				else
					R[i][j] = min (R[i - 1][j], r[i][j]);

				maxx = max (maxx, min ((R[i][j] + L[i][j] - 1), u[i][j]));

			}

	}

	cout << maxx;

	return 0;

}