#3089. Coci2009 ograda

题目描述

给定平面里的 N 个矩形, 每个矩形的边都是和坐标系平行的.
并且满足 每个矩形的下面的边 和 x轴 重合.
从 N 个矩形中删除最多的矩形, 使得 矩形并的区域的边界 保持不变.

.jpg)

输入格式

第1行: 一个整数 N (1 <= N <= 100, 000)  
第2..N+1行: 每行3个整数 X, W, H, 表示一个矩形.  
            X 表示矩形左边界的x坐标.  
            W 表示矩形的宽度 (右边的x坐标 - 左边的x坐标)  
            H 表示矩形的高度 (上边的y坐标 - 下边的y坐标)

            没有两个矩形是 完全重合 (X W H 都完全一样) 的.  
            0 <= X, W, H <= 10^9  
            所有矩形标号为 1..N

输出格式

第1行: 最少留下的矩形数量 B  

样例

样例输入

6  

15 8 4  

10 8 3  

25 3 7  

3 9 5  

1 5 3  

7 2 2  

样例输出

5

数据范围与提示