在皈依基督教后，据信立陶宛第一位也是唯一一位国王明道加斯（Mindaugas）下令建造了维尔纽斯大教堂。教堂的建设已基本完成，只剩下地面需要铺设陶瓷装饰釉面砖。

维尔纽斯大教堂的地面是笛卡尔坐标系中的一个多边形。该多边形有 $N$ 个不同的顶点，编号为 $1$ 到 $N$。对于每个 $1 \le i \le N$，顶点 $i$ 位于点 $(X[i], Y[i])$，其中 $X[i]$ 和 $Y[i]$ 是非负整数。对于每个 $1 \le i \le N - 1$，顶点 $i$ 和顶点 $i + 1$ 之间有一条边，顶点 $N$ 和顶点 $1$ 之间也有一条边。顶点按顺时针或逆时针顺序排列。

该教堂是一个轴对齐多边形，这意味着每一条边都平行于 $x$ 轴或 $y$ 轴。此外，该教堂是一个简单多边形，即： 每个顶点恰好有两条边相交； 任意两条边只能在顶点处相交。

教堂的建造者有无限多的瓷砖。每块瓷砖都是边长为 $2$ 的正方形。建造者希望用这些瓷砖覆盖教堂的很大一部分。具体来说，建造者想要选择一条垂直线，并覆盖教堂位于该线左侧的部分。对于任意整数 $k$，令 $L_k$ 表示由 $x$ 坐标等于 $k$ 的点组成的垂直线。教堂位于 $L_k$ 左侧部分的覆盖是指在平面上放置若干瓷砖，使得： 位于多边形内部且 $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$，使得 $k \le M$ 且存在一种覆盖教堂位于 $L_k$ 左侧部分的方法。

样例

样例输入 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

样例输出 1

2

说明 1

下图展示了 $k = 2$ 时教堂位于 $L_k$ 左侧的部分：

存在一种覆盖教堂位于 $L_2$ 左侧部分的方法。该覆盖使用了两块瓷砖。对于任何 $k > 2$，不存在覆盖教堂位于 $L_k$ 左侧部分的方法。

样例输入 2

4 3
0 0
0 3
3 3
3 0

样例输出 2

0

说明 2

不存在正整数 $k$ 使得教堂位于 $L_k$ 左侧的部分可以用瓷砖覆盖。

样例输入 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

样例输出 3

6

说明 3

如下图所示，可以覆盖教堂位于 $L_6$ 左侧的部分：

对于每个 $k > 6$，不存在覆盖教堂位于 $L_k$ 左侧部分的方法。

数据范围

• $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, \dots, x_N$ 的最小值为 $0$，最大值为 $M$。

子任务