H. 套娃 - 2023 年 “图森未来杯” 全国高校程序设计网络邀请赛

仪表盘所有提交榜单题解

单点时限: 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 \leq n \leq 10^{5}$ ），代表套娃的数量。

接下来的 $n$ 行，每行包含四个整数 $a_{i}, b_{i}, c_{i}, w_{i}$ ，表示第 $i$ 个套娃的长度、宽度、高度。其中 $1 \leq a_{i}, b_{i}, c_{i} \leq 10^{9}$ , $0 \leq w_{i} \leq 10^{9}$ 。

输出格式

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

样例

Input

Output

提示

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

NaN

A. 命题人的疏忽 B. 社恐的舞会 I C. 摇钱树 D. 开灯 E. 社恐的舞会 II F. 龟速飞行棋 G. 切蛋糕 H. 套娃 I. 宝箱

比赛状态发生变化，点 OK 刷新。

OK

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

输入格式

输出格式

样例

提示

题目列表

服务

开源

关于我们