#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
const ll inf = LONG_LONG_MAX / 2;
template <class T> int sgn(T x) { return (x > 0) - (x < 0); }
template<class T>
struct Point {
typedef Point P;
T x, y;
explicit Point(T x=0, T y=0) : x(x), y(y) {}
bool operator<(P p) const { return tie(x,y) < tie(p.x,p.y); }
bool operator==(P p) const { return tie(x,y)==tie(p.x,p.y); }
P operator+(P p) const { return P(x+p.x, y+p.y); }
P operator-(P p) const { return P(x-p.x, y-p.y); }
P operator*(T d) const { return P(x*d, y*d); }
P operator/(T d) const { return P(x/d, y/d); }
T dot(P p) const { return x*p.x + y*p.y; }
T cross(P p) const { return x*p.y - y*p.x; }
T cross(P a, P b) const { return (a-*this).cross(b-*this); }
T dist2() const { return x*x + y*y; }
double dist() const { return sqrt((double)dist2()); }
// angle to x-axis in interval [-pi, pi]
double angle() const { return atan2(y, x); }
P unit() const { return *this/dist(); } // makes dist()=1
P perp() const { return P(-y, x); } // rotates +90 degrees
P normal() const { return perp().unit(); }
// returns point rotated 'a' radians ccw around the origin
P rotate(double a) const {
return P(x*cos(a)-y*sin(a),x*sin(a)+y*cos(a)); }
friend ostream& operator<<(ostream& os, P p) {
return os << "(" << p.x << "," << p.y << ")"; }
};
typedef Point<ll> P;
template<class T>
T polygonArea2(vector<Point<T>>& v) {
T a = v.back().cross(v[0]);
rep(i,0,sz(v)-1) a += v[i].cross(v[i+1]);
return a;
}
struct event {
ll x, l, r;
bool stop;
event(ll x, ll l, ll r, bool stop) : x(x), l(l), r(r), stop(stop) { }
bool operator<(const event &o) const {
return x < o.x;
}
};
struct segtree {
struct node {
bool lp = false, rp = false, mp = false, has = false, full = false;
bool lazy = false, lz_val = false;
};
ll nt = 0;
vector<node> tree;
segtree(ll n) {
nt = 1;
while (nt < n) nt *= 2;
tree = vector<node>(2*nt);
}
void prop(ll k) {
if (!tree[k].lazy) return;
tree[k].has = tree[k].full = tree[k].lz_val;
tree[k].mp = false;
if (!tree[k].lz_val) tree[k].lp = tree[k].rp = false;
else tree[k].lp = tree[k].rp = (k >= nt);
if (k < nt) {
tree[2*k].lazy = tree[2*k+1].lazy = true;
tree[2*k].lz_val = tree[2*k+1].lz_val = tree[k].lz_val;
}
tree[k].lazy = false;
}
void recalc(ll k) {
if (k >= nt) return;
tree[k].has = tree[2*k].has || tree[2*k+1].has;
tree[k].full = tree[2*k].full && tree[2*k+1].full;
if (tree[2*k].full && tree[2*k+1].full) {
tree[k].lp = tree[k].rp = tree[k].mp = false;
}
else if (!tree[2*k].full && !tree[2*k+1].full) {
tree[k].lp = tree[2*k].lp;
tree[k].rp = tree[2*k+1].rp;
tree[k].mp = tree[2*k].mp || tree[2*k+1].mp || (tree[2*k].rp != tree[2*k+1].lp);
}
else if (tree[2*k].full && !tree[2*k+1].full) {
tree[k].lp = (tree[2*k].lp != tree[2*k+1].lp);
tree[k].rp = tree[2*k+1].rp;
tree[k].mp = tree[2*k+1].mp;
}
else if (!tree[2*k].full && tree[2*k+1].full) {
tree[k].lp = tree[2*k].lp;
tree[k].rp = (tree[2*k].rp != tree[2*k+1].rp);
tree[k].mp = tree[2*k].mp;
}
}
bool range_has(ll l, ll r) { return range_has(1, 0, nt-1, l, r); }
bool range_has(ll k, ll tl, ll tr, ll l, ll r) {
prop(k);
if (r < tl || l > tr) return false;
if (l <= tl && r >= tr) return tree[k].has;
ll mid = tl + (tr - tl) / 2;
return range_has(2*k, tl, mid, l, r) || range_has(2*k+1, mid+1, tr, l, r);
}
void range_set(ll l, ll r) { return range_set(1, 0, nt-1, l, r); }
void range_set(ll k, ll tl, ll tr, ll l, ll r) {
prop(k);
if (r < tl || l > tr) return;
if (l <= tl && r >= tr) {
tree[k].lazy = true;
tree[k].lz_val = true;
prop(k);
return;
}
ll mid = tl + (tr - tl) / 2;
range_set(2*k, tl, mid, l, r);
range_set(2*k+1, mid+1, tr, l, r);
recalc(k);
}
void range_unset(ll l, ll r) { return range_unset(1, 0, nt-1, l, r); }
void range_unset(ll k, ll tl, ll tr, ll l, ll r) {
prop(k);
if (r < tl || l > tr) return;
if (l <= tl && r >= tr) {
tree[k].lazy = true;
tree[k].lz_val = false;
prop(k);
return;
}
ll mid = tl + (tr - tl) / 2;
range_unset(2*k, tl, mid, l, r);
range_unset(2*k+1, mid+1, tr, l, r);
recalc(k);
}
bool is_legal() {
prop(1);
return !tree[1].lp && !tree[1].rp && !tree[1].mp;
}
void bake(ll k) {
prop(k);
if (k >= nt) return;
bake(2*k);
bake(2*k+1);
}
};
void solve() {
ll n, _; cin >> n >> _;
vector<P> pts(n);
vector<ll> ys;
for (auto &p : pts) cin >> p.x >> p.y, ys.push_back(p.y);
sort(all(ys)); ys.erase(unique(all(ys)), ys.end());
for (auto &[x, y] : pts) y = lower_bound(all(ys), y) - ys.begin();
ll ly = 0;
for (auto &y : ys) {
ll d = y - ly;
if (d == 0) continue;
if (d & 1) d = 1;
else d = 2;
ly = y = ly + d;
}
for (auto &[x, y] : pts) y = ys[y];
if (polygonArea2(pts) < 0) reverse(all(pts));
vector<event> events;
for (ll i = 0; i < n; i++) {
ll j = (i + 1) % n;
if (pts[i].y == pts[j].y) continue;
if (pts[i].y > pts[j].y) { // start
events.emplace_back(pts[i].x, pts[j].y, pts[i].y - 1, false);
}
else { // stop
events.emplace_back(pts[i].x, pts[i].y, pts[j].y - 1, true);
}
}
sort(all(events));
ll res = 0;
segtree even(ys.back() + 2), odd(ys.back() + 2);
vector<bool> lx(sz(events));
lx.back() = true;
ll ppx = 0;
for (ll i = 0; i+1 < sz(events); i++) lx[i] = (events[i].x != events[i+1].x);
for (ll i = 0; i < sz(events); i++) {
auto [x, l, r, stop] = events[i];
segtree &t = ((x & 1) ? odd : even);
segtree &o = ((x & 1) ? even : odd);
if (ppx != x) {
ppx = x;
if (t.range_has(0, inf) == 0) res = max(res, x-1);
if (o.range_has(0, inf) == 0) res = max(res, x);
}
if (!stop) {
t.range_set(l, r);
}
else {
if (o.range_has(l, r) > 0) break;
t.range_unset(l, r);
}
if (lx[i]) {
if (!t.is_legal() || !o.is_legal()) break;
}
}
cout << res << '\n';
}
signed main() {
cin.tie(0)->sync_with_stdio(0);
solve();
}
