#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ii = pair<int, int>;
using iii = tuple<int, int, int>;
#define pb push_back
#define eb emplace_back
#define mt make_tuple
int N, M, ans, odd_len, x[200005], y[200005], cnt[2];
map<int, vector<ii> > vec;
vector<int> dist_x;
set<iii> s;
int main() {
//~ ios::sync_with_stdio(0);
//~ cin.tie(0);
cin >> N >> M;
for (int i = 1; i <= N; i++) {
cin >> x[i] >> y[i];
}
for (int i = 1; i <= N; i++) {
int j = (i % N) + 1;
if (x[i] == x[j]) {
vec[x[i]].eb(min(y[i], y[j]), max(y[i], y[j]));
}
dist_x.pb(x[i]);
if (x[i] > 0) {
dist_x.pb(x[i] - 1);
}
}
sort(dist_x.begin(), dist_x.end());
dist_x.erase(unique(dist_x.begin(), dist_x.end()), dist_x.end());
for (auto x : dist_x) {
if (cnt[!(x % 2)] == 0) {
ans = x;
}
for (auto [l, r] : vec[x]) {
vector<set<iii>::iterator> to_erase;
vector<iii> to_insert;
// insert (x % 2, l, r)
auto it = s.lower_bound(mt(l, -1, -1));
if (it != s.begin()) {
--it;
auto [l2, r2, p2] = *it;
assert(l2 < l);
if (l < r2) {
to_erase.pb(it);
to_insert.eb(l2, l, p2);
to_insert.eb(l, r2, p2);
}
}
for (auto it : to_erase) {
if (s.find(*it) == s.end()) {
continue;
}
cnt[get<2>(*it)]--;
if ((get<1>(*it) - get<0>(*it)) % 2 == 1) {
odd_len--;
}
s.erase(it);
}
for (auto v : to_insert) {
cnt[get<2>(v)]++;
if ((get<1>(v) - get<0>(v)) % 2 == 1) {
odd_len++;
}
s.insert(v);
}
to_erase.clear();
to_insert.clear();
it = s.lower_bound(mt(r, -1, -1));
if (it != s.begin()) {
--it;
auto [l2, r2, p2] = *it;
assert(l2 < r);
if (r < r2) {
to_erase.pb(it);
to_insert.eb(l2, r, p2);
to_insert.eb(r, r2, p2);
}
}
for (auto it : to_erase) {
if (s.find(*it) == s.end()) {
continue;
}
cnt[get<2>(*it)]--;
if ((get<1>(*it) - get<0>(*it)) % 2 == 1) {
odd_len--;
}
s.erase(it);
}
for (auto v : to_insert) {
cnt[get<2>(v)]++;
if ((get<1>(v) - get<0>(v)) % 2 == 1) {
odd_len++;
}
s.insert(v);
}
to_erase.clear();
for (auto it = s.lower_bound(mt(l, -1, -1)); it != s.end() && get<1>(*it) <= r; it++) {
auto [l2, r2, p2] = *it;
if (p2 != (x % 2)) {
cout << ans << '\n';
return 0;
}
to_erase.pb(it);
}
for (auto it : to_erase) {
if (s.find(*it) == s.end()) {
continue;
}
cnt[get<2>(*it)]--;
if ((get<1>(*it) - get<0>(*it)) % 2 == 1) {
odd_len--;
}
s.erase(it);
}
bool should_insert = to_erase.empty();
if (should_insert) {
to_erase.clear();
int lef = l, rig = r;
it = s.lower_bound(mt(l, -1, -1));
if (it != s.begin()) {
--it;
auto [l2, r2, p2] = *it;
if (l == r2 && (x % 2) == p2) {
to_erase.pb(it);
lef = l2;
}
}
it = s.lower_bound(mt(r, -1, -1));
if (it != s.end()) {
auto [l2, r2, p2] = *it;
if (r == l2 && (x % 2) == p2) {
to_erase.pb(it);
rig = r2;
}
}
for (auto it : to_erase) {
if (s.find(*it) == s.end()) {
continue;
}
cnt[get<2>(*it)]--;
if ((get<1>(*it) - get<0>(*it)) % 2 == 1) {
odd_len--;
}
s.erase(it);
}
cnt[x % 2]++;
if ((rig - lef) % 2 == 1) {
odd_len++;
}
s.emplace(lef, rig, x % 2);
}
}
if (odd_len) {
cout << ans << '\n';
return 0;
}
}
cout << ans << '\n';
}
