#include<bits/stdc++.h>
using namespace std;
#ifdef DEBUG
auto& operator <<(auto& o, pair<auto, auto> p) {return o<<"{"<<p.first<<", "<<p.second<<"}";}
auto& operator <<(auto& o, auto x) {o<<"{"; for(auto v : x) o<<v<<", "; return o<<"}";}
#define debug(X) cerr<<"["#X"]: "<<X<<endl;
#else
#define debug(X) {}
#endif
int32_t main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
set<pair<int, int> > segs[2]; //.first = koniec, .second = poczatek
vector<int> np(2);
int result = 0;
auto add = [&](int x, int y1, int y2)
{
x = x%2;
auto it = segs[x].insert({y2, y1}).first;
if(abs(y2 - y1)%2 == 1) np[x]++;
if(it != segs[x].begin())
{
it--;
if(it->first == y1)
{
if(abs(it->first - it->second)%2 == 1) np[x]--;
if(abs(y2 - y1)%2 == 1) np[x]--;
segs[x].erase(make_pair(it->first, it->second));
segs[x].erase(make_pair(y2, y1));
y1 = it->second;
it = segs[x].insert(make_pair(y2, y1)).first;
if(abs(y2 - y1)%2 == 1) np[x]++;
}
else
it++;
}
it++;
if(it != segs[x].end())
{
if(it->second == y2)
{
if(abs(it->first - it->second)%2 == 1) np[x]--;
if(abs(y1 - y2)%2 == 1) np[x]--;
segs[x].erase(make_pair(it->first, it->second));
segs[x].erase(make_pair(y2, y1));
y2 = it->first;
segs[x].insert(make_pair(y2, y1));
if(abs(y2 - y1)%2 == 1) np[x]++;
}
}
};
auto sub = [&](int x, int y1, int y2)
{
x = x%2; x^=1;
auto it1 = segs[x].lower_bound(make_pair(y1+1, -1));
if(it1 != segs[x].end() && it1->second <= y1) {cout<<result; exit(0);}
auto it2 = segs[x].lower_bound(make_pair(y2+1, -1));
if(it2 != segs[x].end() && it2->second < y2) {cout<<result; exit(0);}
if(it1 != it2) {cout<<result; exit(0);}
x^=1;
vector<pair<int, int> > toAdd;
vector<pair<int, int> > toSub;
for(auto it = segs[x].lower_bound(make_pair(y1+1, -1)); it != segs[x].end()
&& it->second <= y2; ++it)
{
toSub.push_back(*it);
if(abs(it->first - it->second)%2 == 1) np[x]--;
if(it->second < y1)
{
if(abs(it->second - y1)%2 == 1) np[x]++;
toAdd.push_back(make_pair(y1, it->second));
}
if(it->first > y2)
{
if(abs(it->first - y2)%2 == 1) np[x]++;
toAdd.push_back(make_pair(it->first, y2));
}
}
for(auto v : toSub) segs[x].erase(v);
for(auto v : toAdd) segs[x].insert(v);
};
int n, m;
cin>>n>>m;
vector<pair<int, int> > pts(n);
for(auto& v : pts) {cin>>v.first>>v.second;}
auto cmp = [&](pair<int, int> a, pair<int, int> b) {
long long ax = a.first, ay = a.second, bx = b.first, by = b.second;
return ax*by - ay*bx;
};
long long area = 0;
for(int i=0;i<n;i++) area += cmp(pts[i], pts[(i+1)%n]);
if(area < 0) reverse(pts.begin(), pts.end());
debug(pts);
vector<pair<pair<int, bool>, pair<int, int> > > events;
for(int i=0;i<n;i++)
{
if(pts[i].first != pts[(i+1)%n].first) continue;
pair<pair<int, bool>, pair<int, int> > toAdd;
if(pts[i].second < pts[(i+1)%n].second)
{toAdd.second = make_pair(pts[i].second, pts[(i+1)%n].second);}
else toAdd.second = make_pair(pts[(i+1)%n].second, pts[i].second);
if(pts[i].second < pts[(i+1)%n].second) toAdd.first.second = 1;
if(pts[i].second > pts[(i+1)%n].second) toAdd.first.second = 0;
toAdd.first.first = pts[i].first;
events.push_back(toAdd);
}
sort(events.begin(), events.end());
result = events[0].first.first;
int prev = -1;
for(auto& v : events)
{
debug(v);
debug(segs[0]);
debug(segs[1]);
if(prev != v.first.first)
{
if(np[0] != 0 || np[1] != 0) break;
if(np[0] == 0 && np[1] == 0 && segs[(v.first.first%2)^1].size() == 0)
{result = v.first.first;}
else if(np[0] == 0 && np[1] == 0 && segs[(v.first.first%2)].size() == 0)
result = v.first.first-1;
}
if(v.first.second == 0) add(v.first.first, v.second.first, v.second.second);
if(v.first.second == 1) sub(v.first.first, v.second.first, v.second.second);
// if(&v == &events[events.size()-1]) continue;
// if((*(&v + 1)).first.first != v.first.first)
// if(np[0] == 0 && np[1] == 0 && segs[(v.first.first+1)%2].size() == 0)
prev = v.first.first;
}
// if(np[0] == 0 && np[1] == 0 && segs[0].size() == 0 && segs[1].size() == 0) result = m+1;
cout<<result;
}
