题目描述

农夫约翰的奶牛们最喜欢日落时分，因为这时可以看到远处城市的天际线。贝西想知道这座城市最少有多少栋建筑物。请你编写一个程序，根据给定的天际线轮廓，帮助奶牛们计算出城市中最少的建筑物数量。

这座城市的天际线由一系列盒子形状的建筑物组成。天际线的宽度在$1$到$W$个单位之间$（1 ≤ W ≤ 1,000,000）$，并由$N$个连续的$x$和$y$坐标$（1 ≤ x ≤ W，0 ≤ y ≤ 500,000）$描述，这些坐标表示天际线在某个点的高度变化。

例如，以下天际线：

..........................
.....XX.........XXX.......
.XXX.XX.......XXXXXXX.....
XXXXXXXXXX....XXXXXXXXXXXX

可以编码为坐标序列：$(1,1), (2,2), (5,1), (6,3), (8,1), (11,0), (15,2), (17,3), (20,2), (22,1)$。

这个天际线至少需要$6$栋建筑物才能形成。下面是一种可能的6栋建筑物的组合方式：

.......................... ..........................
.....22.........333....... .....XX.........XXX.......
.111.22.......XX333XX..... .XXX.XX.......5555555.....
X111X22XXX....XX333XXXXXXX 4444444444....5555555XXXXX
..........................
.....XX.........XXX.......
.XXX.XX.......XXXXXXX.....
XXXXXXXXXX....666666666666

输入格式

• 第$1$行：两个用空格分隔的整数$N$和$W$（$N$表示坐标点数量，$W$表示天际线宽度）
• 第$2$行到第$N+1$行：每行两个用空格分隔的整数$x$和$y$，表示天际线高度变化的坐标点。$x$坐标严格递增，且第一个$x$坐标始终为$1$。

输出格式

• 第$1$行：一个整数，表示形成该天际线所需的最少建筑物数量。

输入样例

10 26
1 1
2 2
5 1
6 3
8 1
11 0
15 2
17 3
20 2
22 1

输出样例

6

提示

输入解释： 即题目描述中提到的示例情况。

题目来源

USACO 2005 November Silver