#8329. 「JXOI CSP Round 2」纸张 暂未评定

时间限制:1000 ms 内存限制:128 MiB 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: jxy2012

题目描述

日本建筑都是以旧结构形式建造的:房屋互相紧挨着,之间没有空间。它们共同形成了一条长长的,从东向西延伸的街道(房屋的高度不一)。人们将这些房子用纸覆盖住。并且纸的数量越少越好,纸是长方形的。纸可以有公共边,但不能重叠,每一张纸都必须贴近墙并且这些房子必须被覆盖(意思是:纸需要将一侧全部覆盖,并且不能超出街道)。

求最少需要几张海报。

输入格式

第一行为一个整数 ,表示有 个房屋,接下来 行中,第 行表示第 个房屋的宽 与高 ,中间由一个空格隔开。

输出格式

一个整数,表示最少需要几张纸。

样例

样例输入

5
1 2
1 3
2 2
2 5
1 4

样例输出

4

数据范围与提示

对于 的数据,