P3467 [POI2008] PLA-Postering

题目描述

Byteburg 市东边的建筑都是以旧结构形式建造的：建筑互相紧挨着，之间没有空间。

它们共同形成了一条长长的，从东向西延伸的建筑物链（建筑物的高度不一）。

Byteburg 市的市长Byteasar，决定将这个建筑物链的一侧用海报覆盖住，并且想用最少的海报数量，海报是矩形的。

海报与海报之间不能重叠，但是可以相互挨着（即它们具有公共边），每一个海报都必须贴近墙并且建筑物链的整个一侧必须被覆盖（意思是：海报需要将一侧全部覆盖，并且不能超出建筑物链）。

输入格式

第一行为一个整数 $n$ $(1≤n≤250000)$， 表示有 $n$ 个建筑。

接下来 $n$ 行中， 第 $i$ 行表示第 $i$ 个建筑物的宽 $d_i$ 与高 $w_i$ $(1≤d_i,w_i≤10^9)$，中间由一个空格隔开。

输出格式

一个整数，表示最少需要几张海报。

样例 #1

样例输入 #1

5
1 2
1 3
2 2
2 5
1 4

样例输出 #1

4

提示

题目简述：$N$ 个矩形，排成一排。现在希望用尽量少的矩形海报遮住它们。