Problem4403--偏序集

4403: 偏序集

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 256 MiB

Description

有 $n$ 个三元组,第 $i$ 个三元组是 $(x_i, y_i, z_i)$。如果 $A=(u, v, w)$ 和 $B=(x, y, z)$ 满足 $u \leq x, v \leq y, w \leq z$,我们称为 $A \leq B$,也可以说 $B \geq A$。这时,我们说 $A$ 与 $B$ 是可比较的。
例如 $(1, 2, 3)$ 和 $(2, 3, 3)$ 是可比较的。但是 $(3, 2, 3)$ 和 $(2, 3, 4)$ 是不可比较的。我们没法比较它们的大小。
给出 $n$ 个三元组,从其中选出若干三元组,使得选出的三元组两两可以比较。求最多选出多少个三元组。

Input

第一行输入一个整数 $n$。$1 ≤ n≤1,000,000$。
接下来 $n$ 行,第 $i$ 行三个正整数表示 $x_i, y_i, z_i$。数据范围不会超过 $10^{18}$。

Output

一行一个数,最多选出多少个三元组。

Sample 1 Input

4
5 5 2
3 3 2
1 6 2
1 1 1

Sample 1 Output

3

HINT

【样例说明】
选出第 $1$、$2$、$4$ 三个三元组。

Source/Category

基础算法 4.120.动态规划