题目描述

题目译自 XV OI Olimpiada Informatyczna – I etap Plakatowanie

拜托城东部的所有建筑物遵循古老的拜托建筑原则：它们紧密相连，毫无间隙，共同形成一堵从东到西绵延的墙面，高度各异。

市长 Bajtazar 决定用海报覆盖这堵墙的北侧墙面。他希望探究最少需要多少海报才能完全覆盖整面北墙。海报需为边沿垂直和水平的矩形，彼此不可重叠，但可边对边接触。每张海报必须完全贴合某些建筑物的墙面，且北侧墙面需被全部覆盖。

编写程序：

• 从标准输入读取建筑物描述。
• 计算完全覆盖北侧墙面所需的最少海报数量。
• 将结果输出到标准输出。

输入格式

第一行包含一个整数 $n$ $(1 \leq n \leq 250000)$，表示并排建筑物的数量。接下来的 $n$ 行，每行包含两个整数 $d_i, w_i$ $(1 \leq d_i, w_i \leq 1000000000)$，用单空格分隔，分别表示第 $i$ 座建筑物的宽度和高度。

输出格式

输出一行，包含一个整数，表示完全覆盖建筑物北侧墙面所需的最少矩形海报数量。

5
1 2
1 3
2 2
2 5
1 4

4

图示展示了建筑物北侧墙面。第二个图展示了一个使用四张海报覆盖墙面的示例。