问题 1420. -- 垒箱子

1420: 垒箱子

时间限制: 2 Sec  内存限制: 128 MB
提交: 284  解决: 35
[提交][状态][讨论版]

题目描述

Mr.Q某天闲得无聊,搬来了若干个长方体状箱子,想把它们垒起来,他希望箱子垒得尽可能高,但是又希望箱子能足够稳定,他发现,只要对于所有箱子,上面的箱子严格不大于下面的箱子,那么就一定是稳定的

这里严格不大于于指的是,上层箱子的长不大于下层箱子的长,上层箱子的宽不大于下层箱子的宽。

请问箱子最高可以垒多高?

输入

第一行一个数字n,表示箱子的数量

接下来n行,

第 i 行给出第i个箱子三组棱(每组棱为4条平行边)的信息ai,bi,ci

输出

一个数字H,表示垒的最高高度

样例输入

2
1 3 3
2 2 4

样例输出

5

提示

1 <= n <= 30

1<= a_i,b_i,c_i <=1e7 且在这个范围内随机生成

来源

[提交][状态][讨论版]