Tiles

Soon after converting to Christianity, the first and only Lithuanian king, Mindaugas, is believed to have ordered the construction of the Vilnius Cathedral. The construction is nearly complete. Only the floor remains, and it must be covered with ornamented glazed ceramic tiles.

The cathedral floor is a polygon in a 2D plane with a Cartesian coordinate system. The polygon has $N$ distinct vertices, numbered from 1 to $N$. For each $1 \le i \le N$, vertex $i$ is at point $(X_i, Y_i)$, where $X_i$ and $Y_i$ are nonnegative integers. Vertex $i$ is joined to vertex $i+1$ for each $1 \le i \le N-1$, and vertex $N$ is joined to vertex 1. The vertices are listed in either clockwise or counterclockwise order.

The cathedral is an axis-aligned polygon: every edge is parallel to the $x$-axis or the $y$-axis. It is also simple. Exactly two edges meet at each vertex, and any two edges meet only at a shared vertex.

The builders have infinitely many square tiles, each with side length 2. They pick a vertical line and want to cover the part of the cathedral to the left of it. For any integer $k$, let $L_k$ be the vertical line with $x$-coordinate $k$. A covering of the part left of $L_k$ is a placement of tiles in the plane such that:

• every point inside the polygon with $x$-coordinate less than $k$ is covered by some tile;
• no point outside the polygon, or with $x$-coordinate greater than $k$, is covered by any tile;
• the interiors of the tiles do not overlap.

The minimum $x$-coordinate of any vertex is 0. Let $M$ be the maximum $x$-coordinate of any vertex. Find the largest integer $k$ with $k \le M$ such that a covering of the part left of $L_k$ exists. By definition, a covering of the part left of $L_0$ exists, using 0 tiles.

The first line contains two integers $N$ and $M$, the number of vertices and the maximum $x$-coordinate of any vertex. Each of the next $N$ lines contains two integers $x_i$ and $y_i$, the coordinates of vertex $i$.

Print the maximum $k$ such that $k \le M$ and a covering of the part of the cathedral to the left of $L_k$ exists.

• $4 \le N \le 2 \cdot 10^5$
• $1 \le M \le 10^9$
• $0 \le y_i \le 10^9$ for each $1 \le i \le N$
• The cathedral forms an axis-aligned simple polygon.
• The minimum of $x_1, x_2, \dots, x_N$ is 0, and the maximum is $M$.