城市天际线（Skyline）

题目描述

对 Farmer John 的奶牛们来说，一天中最美好的时刻就是太阳落山的时候。她们可以看到远处城市的天际线。Bessie 想知道这座城市至少有多少栋建筑。

城市的侧面轮廓由若干个矩形建筑组成。给定城市最终呈现出的天际线轮廓，请你计算形成该轮廓所需的最少建筑数量。

天际线的宽度在 1 到 W 之间，其中 1 <= W <= 1,000,000。天际线由 N 个连续的坐标点描述，其中 1 <= N <= 50,000。每个坐标点为 (x, y)，表示从横坐标 x 开始，天际线高度变为 y。

坐标范围如下：

• 1 <= x <= W
• 0 <= y <= 500,000

输入中的 x 坐标严格递增，并且第一个 x 坐标一定为 1。

例如，下面的天际线：

..........................
.....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

输入格式

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

接下来 N 行，每行包含两个用空格分隔的整数 x 和 y，表示天际线在横坐标 x 处变为高度 y。

输出格式

输出一行，一个整数，表示形成给定天际线所需的最少建筑数量。

样例输入

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

样例输出

6

样例说明

样例对应题目描述中的天际线。形成该天际线至少需要 6 栋矩形建筑。

数据范围

• 1 <= N <= 50,000
• 1 <= W <= 1,000,000
• 1 <= x <= W
• 0 <= y <= 500,000
• 所有 x 坐标严格递增
• 第一个 x 坐标一定为 1