题目描述

题目译自 BalticOI 2024 Day2「Tiles」

据信，立陶宛第一位也是唯一一位国王明道加斯在皈依基督教后不久就下令修建维尔纽斯大教堂。工程已基本完工，只是地面上还需要铺上陶瓷装饰釉面砖。

维尔纽斯大教堂的地面是二维平面直角坐标系下的一个多边形。多边形有 $N$ 个不同的顶点，编号为 $1$ 到 $N$。对于 $1\le i\le N$ 的每个 $i$，顶点 $i$ 位于点 $(X[i],Y[i])$，其中 $X[i]$ 和 $Y[i]$ 均为非负整数。有一条边连接顶点 $i$ 和顶点 $i + 1$（对于每个 $1 \le i \le N - 1$），还有一条边连接顶点 $N$ 和顶点 $1$。顶点按顺时针或逆时针顺序排列。

大教堂是一个轴对齐的多边形，意味着每条边要么平行于 $x$ 轴，要么平行于 $y$ 轴。此外，大教堂还是一个简单多边形，也就是：

• 在每个顶点处恰好有两条边相交；
• 任意一对边只能在顶点处相交。

大教堂的建造者有无限多块瓷砖。每块瓷砖都是边长等于 $2$ 的正方形。建造者希望用这些瓷砖覆盖大教堂的大部分。具体地说，建造者希望选取某条垂直线，并覆盖该线左边的大教堂部分。对于任意整数 $k$，令 $L_k$ 表示由 $x$ 坐标等于 $k$ 的点组成的垂直线。覆盖 $L$ 左侧大教堂的部分就是在平面上放置一定数量的瓷砖，使得：

• 位于多边形内部且 $x$ 坐标小于 $k$ 的每个点都会被某块瓷砖覆盖；
• 位于多边形外部或 $x$ 坐标大于 $k$ 的点都不会被某块瓷砖覆盖；
• 铺设的瓷砖不会重叠。

大教堂中任何顶点的最小 $x$ 坐标都是 $0$，令 $M$ 表示大教堂中任何顶点的最大 $x$ 坐标。

帮助维尔纽斯大教堂的建造者找出最大的整数 $k$，使得 $k \le M$，并且大教堂在 $L_k$ 左边的部分存在一个覆盖。请注意，根据定义，大教堂在 $L_0$ 左边的部分存在一个覆盖（使用了 $0$ 块瓷砖）。

输入格式

第一行包含两个整数 $N$ 和 $M$，分别表示顶点个数和所有顶点 $x$ 坐标的最大值。

接下来 $N$ 行，第 $i$ 行包含两个整数 $x_i$ 和 $y_i$，表示第 $i$ 个顶点的坐标。顶点按顺时针或逆时针顺序排列。

输出格式

输出满足 $k\le M$ 的最大 $k$，使得 $L_k$ 左边存在一个覆盖。

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

2

4 3
0 0
0 3
3 3
3 0

0

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

6

数据范围与提示

对于所有数据，满足：

• $4\le N\le 2\cdot 10^5$
• $1\le M\le 10^9$
• $0\le y_i\le 10^9$（对于每个 $1\le i\le N$）
• 大教堂形成了一个轴对齐的简单多边形
• $x_1,x_2,\ldots,x_N$ 的最小值为 $0$，最大值为 $M$

详细子任务附加限制及分值如下表所示。