5041. 套娃

单点时限: 3.0 sec

内存限制: 1024 MB

Cuber QQ 想为 Quber CC 的生日准备一件礼物。他买了 $n$ 个套娃,第 $i$ 个套娃的长度、宽度、高度分别是 $a_i,b_i,c_i$,重量是 $w_i$ 。当且仅当 $a_i<a_j$ 且 $b_i<b_j$ 且 $c_i<c_j$ 同时满足的时候, 第 $i$ 个套娃可以被装进第 $j$ 个套娃里。每一个套娃中最多装一个别的套娃。

Cuber QQ 想要给 Quber CC 送一个他所能组装成的最重的套娃(内部可能套了许多层),请你告诉他最重的套娃有多重。

输入格式

第一行包含一个整数 $n$($1\le n \le 10^5$),代表套娃的数量。

接下来的 $n$ 行,每行包含四个整数 $a_i,b_i,c_i,w_i$ ,表示第 $i$ 个套娃的长度、宽度、高度。其中 $1\le a_i,b_i,c_i\le 10^9$, $0\le w_i\le 10^9$。

输出格式

输出共一行,包含一个整数,表示组装成的最重的套娃有多重。

样例

Input
5
1 2 3 1
2 2 2 2
3 4 5 3
2 3 4 2
3 3 3 3
Output
6

提示

在样例中,Cuber QQ 可以将第一个套娃放进第四个套娃 ,然后把第四个套娃放进第三个套娃。组装成的套娃重量是 $6$ 。

62 人解决,168 人已尝试。

104 份提交通过,共有 913 份提交。

5.8 EMB 奖励。

创建: 1 年,6 月前.

修改: 1 年,6 月前.

最后提交: 2 月,4 周前.

来源: N/A

题目标签