[POI 2008] PLA-海报张贴

题目描述

比特堡东区的所有建筑都按照古老的工艺建造：它们紧密相连，中间没有任何空隙。这些建筑形成了一长串高度各不相同的建筑群，从东延伸到西。

比特堡市长比泰萨尔决定用海报覆盖这一整排建筑的北墙面。比泰萨尔想要知道覆盖整个北墙面所需的最少海报数量。 海报是矩形，边为竖直和水平方向。海报不能重叠，但可以相邻（即边缘可以接触）。每张海报必须完全贴在建筑墙面上，且要把所有建筑的北墙面完全覆盖。

任务

编写程序完成以下要求：

• 从标准输入读取建筑信息；
• 计算完全覆盖建筑北墙面所需的最少矩形海报数量；
• 将结果输出到标准输出。

输入格式

第一行输入一个整数 $n$（$1\le n\le 250\ 000$），表示建筑的数量。

接下来 $n$ 行，每行两个整数 $d_i$ 和 $w_i$（$1\le d_i,w_i\le 1\ 000\ 000\ 000$），用空格分隔，分别表示第 $i$ 栋建筑的长度和高度。

输出格式

仅输出一行一个整数，表示覆盖所有建筑北墙面所需的最少海报数量。

输入样例1：

5
1 2
1 3
2 2
2 5
1 4

输出样例1：

4

提示

（暂无提示）

标签：P3467|2008|POI（波兰）|单调栈

来源

P3467|[POI 2008] PLA-Postering