#include <bits/stdc++.h>
using namespace std;
void add(vector<int> arete, int &impair, vector<int> &parity, set<vector<int>> &Intervals)
{
if ((arete[2] - arete[1] + 1) % 2 == 1)
impair++;
parity[arete[0] % 2]++;
Intervals.insert({arete[1], arete[2], arete[0] % 2});
}
int main()
{
int N, M;
cin >> N >> M;
vector<vector<int>> arete;
vector<int> X(N), Y(N);
for (int i = 0; i < N; i++)
{
cin >> X[i] >> Y[i];
}
for (int i = 0; i < N; i++)
{
if (X[(i + 1) % N] == X[i])
{
if (Y[i] < Y[(i + 1) % N])
arete.push_back({X[i], min(Y[i], Y[(i + 1) % N]), max(Y[i], Y[(i + 1) % N]) - 1, 1});
else
arete.push_back({X[i], min(Y[i], Y[(i + 1) % N]), max(Y[i], Y[(i + 1) % N]) - 1, -1});
}
}
sort(arete.begin(), arete.end());
if (arete[0][3] == -1)
for (int i = 0; i < arete.size(); i++)
arete[i][3] = 0 - arete[i][3];
int last = -1;
int impair = 0;
vector<int> parity(2);
int maxx = 0;
set<vector<int>> Intervals;
for (int i = 0; i < arete.size(); i++)
{
if (arete[i][0] != last || i == arete.size() - 1)
{
last = arete[i][0];
if (impair)
break;
if (parity[0] == 0 || parity[1] == 0)
{
int par = ((parity[1]) ? 1 : 0);
maxx = ((arete[i][0] % 2 == par) ? arete[i][0] : (arete[i][0] - 1));
}
}
if (arete[i][3] == 1)
{
auto pos = Intervals.lower_bound({arete[i][1]});
if (pos != Intervals.end() && (*pos)[0] == arete[i][2] + 1 && (*pos)[2] == (arete[i][0] % 2))
{
arete[i][2] = (*pos)[1];
if (((*pos)[1] - (*pos)[0] + 1) % 2 == 1)
impair--;
parity[(*pos)[2]]--;
pos = Intervals.erase(pos);
}
if (pos != Intervals.begin())
{
pos--;
if ((*pos)[1] == arete[i][1] - 1 && (*pos)[2] == (arete[i][0] % 2))
{
arete[i][1] = (*pos)[0];
if (((*pos)[1] - (*pos)[0] + 1) % 2 == 1)
impair--;
parity[(*pos)[2]]--;
Intervals.erase(pos);
}
}
add(arete[i], impair, parity, Intervals);
}
else
{
auto pos = Intervals.upper_bound({arete[i][2], 1000000000});
pos--;
if ((arete[i][0] % 2) != (*pos)[2])
break;
if (arete[i][1] < (*pos)[0])
break;
int left = (*pos)[0], right = arete[i][1] - 1;
if (right >= left)
{
add({(*pos)[2], left, right}, impair, parity, Intervals);
}
left = arete[i][2] + 1, right = (*pos)[1];
if (right >= left)
{
add({(*pos)[2], left, right}, impair, parity, Intervals);
}
parity[(*pos)[2]]--;
if ((((*pos)[1] - (*pos)[0]) % 2) == 0)
impair--;
Intervals.erase(pos);
}
}
cout << maxx;
}
