2023 年 “图森未来杯” 全国高校程序设计邀请赛 - 现场赛

H. 套娃

单点时限: 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$ 。