Coci2009 ograda

时间限制:3s      空间限制:128MB

题目描述

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


输入格式

    第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

提示

没有写明提示


题目来源

没有写明来源