#include <bits/stdc++.h>
using namespace std;
int max_line(int N, int, std::vector<int> X, std::vector<int> Y) {
map<int, vector<pair<int, int>>> lines_at_x;
for (int i = 0; i < N; ++i) {
int j = (i + 1) % N;
if (X[i] == X[j]) {
if (X[i] > 0) {
lines_at_x[X[i] - 1];
}
lines_at_x[X[i]].push_back(make_pair(min(Y[i], Y[j]), max(Y[i], Y[j])));
}
}
int answer = 0;
vector<int> parity_cnt(2);
int odd_lines_cnt = 0;
set<tuple<int, int, int>> current_lines;
map<int, set<tuple<int, int, int>>::iterator> line_ends_at, line_starts_at;
auto erase_current_line = [&] (set<tuple<int, int, int>>::iterator it) {
--parity_cnt[get<2>(*it)];
line_starts_at.erase(get<0>(*it));
line_ends_at.erase(get<1>(*it));
if ((get<1>(*it) - get<0>(*it)) % 2 == 1) {
--odd_lines_cnt;
}
current_lines.erase(it);
};
auto insert_current_line = [&] (int start_line, int end_line, int parity) {
if (line_ends_at.count(start_line)) {
auto it = line_ends_at[start_line];
if (get<2>(*it) == parity) {
start_line = get<0>(*it);
erase_current_line(it);
}
}
if (line_starts_at.count(end_line)) {
auto it = line_starts_at[end_line];
if (get<2>(*it) == parity) {
end_line = get<1>(*it);
erase_current_line(it);
}
}
auto it = current_lines.insert(
make_tuple(start_line, end_line, parity)).first;
++parity_cnt[parity];
line_starts_at[start_line] = it;
line_ends_at[end_line] = it;
if ((end_line - start_line) % 2 == 1) {
++odd_lines_cnt;
}
};
for (auto [x, lines] : lines_at_x) {
if (parity_cnt[1 - x % 2] == 0) {
answer = x;
}
if (lines.size() == 0) {
continue;
}
sort(lines.begin(), lines.end());
int start_line = lines[0].first;
for (int i = 0; i < static_cast<int>(lines.size()); ++i) {
if (i + 1 == static_cast<int>(lines.size()) ||
lines[i].second != lines[i + 1].first) {
int end_line = lines[i].second;
while (start_line < end_line) {
auto it = current_lines.upper_bound(
make_tuple(start_line, INT_MAX, INT_MAX));
bool entering_polygon = false;
if (it == current_lines.begin()) {
entering_polygon = true;
} else {
--it;
if (get<1>(*it) <= start_line) {
entering_polygon = true;
}
}
if (entering_polygon) {
insert_current_line(start_line, end_line, x % 2);
break;
}
int start_cur_line = get<0>(*it);
int end_cur_line = get<1>(*it);
int parity_cur_line = get<2>(*it);
erase_current_line(it);
if (x % 2 != parity_cur_line) {
return answer;
}
if (start_cur_line < start_line) {
insert_current_line(start_cur_line, start_line, x % 2);
}
if (end_line < end_cur_line) {
insert_current_line(end_line, end_cur_line, x % 2);
}
start_line = end_cur_line;
}
if (i + 1 < static_cast<int>(lines.size())) {
start_line = lines[i + 1].first;
}
}
}
if (odd_lines_cnt > 0) {
return answer;
}
}
return answer;
}
#include <cassert>
#include <cstdio>
#include <vector>
int main() {
int N, M;
assert(2 == scanf("%d %d", &N, &M));
std::vector<int> X(N), Y(N);
for (int i = 0; i < N; ++i) {
assert(2 == scanf("%d %d", &X[i], &Y[i]));
}
int result = max_line(N, M, X, Y);
printf("%d\n", result);
return 0;
}
