[POI2008] PLA-Postering

题目描述

Byteburg市东边的建筑都是以旧结构形式建造的:建筑互相紧挨着,之间没有空间.它们共同形成了一条长长的,从东向西延伸的建筑物链(建筑物的高度不一).Byteburg市的市长Byteasar,决定将这个建筑物链的一侧用海报覆盖住.并且想用最少的海报数量,海报是矩形的.海报与海报之间不能重叠,但是可以相互挨着(即它们具有公共边),每一个海报都必须贴近墙并且建筑物链的整个一侧必须被覆盖(意思是:海报需要将一侧全部覆盖,并且不能超出建筑物链)

N个矩形,排成一排. 现在希望用尽量少的矩形海报Cover住它们.

输入格式

第一行给出数字N,代表有N个矩形.N在[1,250000] 下面N行,每行给出矩形的长与宽.其值在[1,1000000000]2 1/2 Postering

输出格式

最少数量的海报数..

样例 #1

样例输入 #1

5
1 2
1 3
2 2
2 5
1 4

样例输出 #1

4

提示

题目简述：N个矩形,排成一排. 现在希望用尽量少的矩形海报Cover住它们.