[Usaco2007 Demo]City skyline

城市的横向位置为整数 $1,2,\ldots,W$ 。城市的地平线由 $N$ 个横坐标严格递增的点 $(x_i,y_i)$ 描述。

对于 $i<N$ ，点 $(x_i,y_i)$ 表示从位置 $x_i$ 到位置 $x_{i+1}-1$ 的地平线高度均为 $y_i$ 。最后一个点 $(x_N,y_N)$ 表示从位置 $x_N$ 到位置 $W$ （含）的地平线高度均为 $y_N$ 。若使用连续坐标表示，上述范围可分别视为区间 $[x_i,x_{i+1})$ 和 $[x_N,W+1)$ 。

地面高度为 $0$ ， $y_i=0$ 表示对应区间内没有建筑。

城市由若干建筑物组成。每座建筑物都是底边位于地面、两侧边竖直且顶边水平的矩形。建筑物在水平方向上可以相邻或重叠，所有建筑物叠加后的外轮廓必须恰好等于给定的城市地平线。

请计算能够形成该地平线的最少建筑物数量。

输入格式

第一行包含两个以空格分隔的整数 $N$ 和 $W$ 。

接下来 $N$ 行，每行包含两个以空格分隔的整数 $x_i$ 和 $y_i$ 。

输入中的 $x_i$ 严格递增，且 $x_1=1$ 。其中， $W$ 是城市包含的最后一个横坐标位置。

输出格式

输出一个整数，表示形成给定城市地平线所需的最少建筑物数量。

样例输入

样例输出

数据范围

$1\le N\le 5\times 10^4$ ；
$1\le W\le 10^9$ ；
$1\le x_i\le W$ ；
$0\le y_i\le 5\times 10^5$ ；
$x_1=1$ ，且 $x_i$ 严格递增。

来源与许可

本题为 USACO 2007 Demo 试题「City Skyline」，题面与测试数据整理自 BZOJ。

样例 1

输入