#include<bits/stdc++.h>
#define L(i, j, k) for(int i = (j); i <= (k); ++i)
#define R(i, j, k) for(int i = (j); i >= (k); --i)
#define ll long long
#define sz(a) ((int) (a).size())
#define vi vector < int >
#define me(a, x) memset(a, x, sizeof(a))
#define ull unsigned long long
#define ld __float128
#define pb emplace_back
using namespace std;
const int N = 1e6 + 7;
struct fenwt {
	int fen[N];
	fenwt() {
		me(fen, 0);
	}
	void add(int p, int w) {
		for(; p < N; p += p & -p)
			fen[p] += w;
	}
	inline int query(int p) {
		int ret = 0;
		for(; p; p -= p & -p) ret += fen[p];
		return ret;
	}
} F;
map<int,vector<pair<int,int>>>mp;
int n, m;
int x[N], y[N];
int arr[N], tot;
vector<pair<int,vector<pair<int,int>>>>vc;
bool hos[N], occ[N];
int odd[N];
struct pm {
	int perm[4];
	bool v1[4], v2[4];
	pm() {
		L(i, 0, 3)perm[i] = i, v1[i] = v2[i] = 0;
	}
};
pm operator + (pm a, pm b) {
	pm c;
	L(i, 0, 3) {
		c.perm[i] = b.perm[a.perm[i]];
		c.v1[i] = a.v1[i] | b.v1[a.perm[i]];
		c.v2[i] = a.v2[i] | b.v2[a.perm[i]];
	}
	return c;
}
pm seg[N][2][2][2]; // col.rev; val.rev; val.(col.rev)
void upd(int x) {
	L(i, 0, 1) L(j, 0, 1) L(k, 0, 1) {
		seg[x][i][j][k] = seg[x * 2][i][j][k] + seg[x * 2 + 1][i][j][k];
	}
}
struct tag {
	int a, b, c;
	tag(int A = 0, int B = 0, int C = 0) {
		a = A, b = B, c = C;
	}
};
tag operator + (tag a, tag b) {
	if(!a.a) return tag(a.a ^ b.a, a.b ^ b.b, a.c ^ b.c);
	else return tag(a.a ^ b.a, a.b ^ b.c, a.c ^ b.b);
}
tag tg[N];
void adt(int x, tag w) {
	if(w.b) L(i, 0, 1) L(k, 0, 1) swap(seg[x][i][0][k], seg[x][i][1][k]);
	if(w.c) L(i, 0, 1) L(j, 0, 1) swap(seg[x][i][j][0], seg[x][i][j][1]);
	if(w.a) L(j, 0, 1) L(k, 0, 1) swap(seg[x][0][j][k], seg[x][1][k][j]);
	tg[x] = tag();
}
void build(int x, int L, int R) {
	if(L == R) {
		L(i, 0, 1) L(j, 0, 1) L(k, 0, 1) {
			int occ = i, hos = k;
			L(t, 0, 3) {
				int ban = 0;
				int hav_one = 0;
				int lst = t % 2, var = t / 2;
				if(occ) {
					if(hos)hav_one = 1;
					if(var == 0) lst = hos;
					else if(lst != hos) ban = 1;
					var ^= 1;
				}
				if(!occ && hos) {
					ban = 1;
				}
				if(!occ && var) {
					ban = 1;
				}
				auto &s = seg[x][i][j][k];
				s.perm[t] = lst + var * 2;
				s.v1[t] = ban;
				s.v2[t] = hav_one;
			}
		}
		return;
	}
	int mid = (L + R) >> 1;
	build(x * 2, L, mid), build(x * 2 + 1, mid + 1, R);
	upd(x);
}
void push(int x) {
	adt(x * 2, tg[x]);
	adt(x * 2 + 1, tg[x]);
	tg[x] = tag();
}
void cov(int x, int L, int R, int l, int r, tag w) {
	if(l <= L && R <= r) {
		adt(x, w);
		return;
	}
	push(x);
	int mid = (L + R) >> 1;
	if(l <= mid) cov(x * 2, L, mid, l, r, w);
	if(r > mid) cov(x * 2 + 1, mid + 1, R, l, r, w);
	upd(x);
}
int main() {
	ios :: sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> n >> m;
	L(i, 1, n) {
		cin >> x[i] >> y[i];
		++y[i];
		arr[++tot] = y[i];
		arr[++tot] = y[i] ^ 1;
		arr[++tot] = y[i] + 2;
		arr[++tot] = (y[i] ^ 1) + 2;
	}
	sort(arr + 1, arr + tot + 1);
	tot = unique(arr + 1, arr + tot + 1) - arr - 1;
	L(i, 1, n) {
		y[i] = lower_bound(arr + 1, arr + tot + 1, y[i]) - arr;
	}
	L(i, 1, n) {
		int nxt = i % n + 1;
		if(x[nxt] == x[i]) {
			mp[x[i]].pb(min(y[i], y[nxt]), max(y[i], y[nxt]));
		}
	}
	for(auto&u : mp) {
		vc.pb(u);
	}
	build(1, 1, tot);
	int ns = 0;
	L(i, 0, sz(vc) - 2) {
		int len = vc[i + 1].first - vc[i].first;
		if(len >= 3) len = len % 2 + 2;
		sort(vc[i].second.begin(), vc[i].second.end());
		for(auto&it : vc[i].second)  
			cov(1, 1, tot, it.first + 1, it.second, tag(1, 0, 0));
		L(t, 1, len) {
			cov(1, 1, tot, 1, tot, tag(0, 1, 0));
			auto dt = seg[1][0][0][0];
			int ban = dt.v1[0];
			int hav_one = dt.v2[0];
			int lst = dt.perm[0] % 2, var = dt.perm[0] / 2;
			if(var)ban = 1;
			if(ban) {
				cout << ns << '\n';
				return 0;
			}
			if(!hav_one) {
				ns = max(ns, vc[i + 1].first - len + t);
			}
		}
	}
	cout << ns << '\n';
	return 0;
}