Problem Description

There is a cathedral with \( N \) vertices, with coordinates \((x_i, y_i)\) for each vertex. For each \( 1 \leq i < N \), there is an edge between vertex \( i \) and \( i+1 \), and additionally, there is an edge between vertex \( N \) and vertex \( 1 \).

The cathedral is an axis-symmetric polygon, meaning each edge is parallel to either the \( x \)-axis or the \( y \)-axis. Furthermore, the cathedral is a simple polygon, which means:

• Each vertex is intersected by exactly two edges.
• Any pair of edges intersect only at vertices.

You have an infinite supply of \( 2 \times 2 \) tiles. You wish to cover most of the cathedral by choosing a vertical line and covering the part of the cathedral to the left of this line. For any integer \( k \), let \( L_k \) be the vertical line containing points with \( x \)-coordinate equal to \( k \). The coverage of the part of the cathedral to the left of \( L_k \) involves placing a certain number of tiles such that:

• Every point inside the polygon with \( x \)-coordinate less than \( k \) is covered by a 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 in the cathedral is \( 0 \). Let \( M \) be the maximum \( x \)-coordinate of any vertex in the cathedral.

You are to find the largest \( k \) (where \( 0 \leq k \leq M \)) that satisfies these conditions. By definition, there is always an answer of \( 0 \).

Input Format

The first line contains two integers \( N \) and \( M \).

The next \( N \) lines each contain two integers \((x_i, y_i)\). These vertices are given in either clockwise or counterclockwise order.

Output Format

Output a single integer \( k \).

Sample Input and Output

Sample Input #1

14 6
0 1
0 3
2 3
2 4
0 4
0 6
3 6
3 7
4 7
6 7
6 5
3 5
3 2
3 1

Sample Output #1

2

Sample Input #2

4 3
0 0
0 3
3 3
3 0

Sample Output #2

0

Sample Input #3

18 9
0 2
2 2
2 1
4 1
4 0
9 0
9 2
4 2
4 4
7 4
7 3
9 3
9 6
4 6
4 5
2 5
2 4
0 4

Sample Output #3

6

Notes/Hints

For all data, \( 4 \leq N \leq 2 \times 10^5 \), \( 1 \leq M \leq 10^9 \), \( 0 \leq y_i \leq 10^9 \), \( \min(\{x_i\}) = 0, \max(\{x_i\}) = M \).

见题面 Input 部分

见题面 Output 部分