AdditionalFile5562.zip

#5562. 「POI2026 R1」Bagaż podręczny

标签: 传统 | 时间限制: 2000 ms | 内存限制: 64 MiB |

题目描述

题目译自 XXXIII Olimpiada Informatyczna – I etap Bagaż podręczny

Bajtazar 即将踏上前往下一届国际信息学奥林匹克的漫长旅程，需要搭乘 $n$ 家航空公司的航班。

每家航空公司对随身行李的最大尺寸都有自己的规定：第 $i$ 家允许的行李必须能放入长方体空间 $A_i \times B_i \times C_i$。

Bajtazar 想购买一个长方体行李箱，尺寸为 $X \times Y \times Z$。

他希望这个行李箱的体积 $X \cdot Y \cdot Z$ 尽可能大，同时在每家航空公司登机前，都可以通过任意旋转（每根轴独立旋转 $90$ 度的任意倍数）使其符合对应航空公司的尺寸限制。

请帮助 Bajtazar 计算出能够满足所有航空公司要求的最大行李箱体积。

输入格式

第一行一个整数 $n$ $(1 \leq n \leq 10^5)$，表示航空公司数量。

接下来 $n$ 行，每行三个整数 $A_i, B_i, C_i$ $(1 \leq A_i, B_i, C_i \leq 10^6)$，表示第 $i$ 家航空公司允许的最大尺寸。

输出格式

仅一行一个整数，表示能带上所有 $n$ 家航空公司航班的最大行李箱体积。

样例 1

输入

2
2 5 3
1 4 4

输出

12

购买 $1 \times 3 \times 4$ 的行李箱，体积为 $12$。

样例 2

输入

6
55 40 23
40 23 55
55 35 25
23 56 35
55 40 23
55 20 40

输出

38500

$55 \times 35 \times 20$ 的行李箱（体积 $38500$）通过适当旋转可以满足所有航空公司的限制。

附加样例

1. $n=10^4$，$A_i=33i$，$B_i=1$，$C_i=1$；答案为 $33$
2. $n=10^5$，$A_i=i$，$B_i=n+1-i$，$C_i=10^6$；答案为 $50001000000$

数据范围与提示

详细子任务附加限制及分值如下表所示：