题目描述

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

输入格式

第一行为一个整数 $n$，表示有 $n$ 个建筑，$1\le n\le 250000$。

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

输出格式

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

123 500

623