题目描述

有 $n$ 条航线，第 $i$ 条航线要求行李能被装进长宽高分别为 $A_i,B_i,C_i$ 的长方体中（边缘可以相切，对于每条航线可以任意旋转）。

现在欲采购一个长宽高分别为 $X,Y,Z$ 的长方体行李箱，最大化其体积（$X\cdot Y\cdot Z$）。求出可能的最大体积。

输入格式

第一行，正整数 $n$（$1\le n\le 10^5$）。

接下来 $n$ 行，每行三个正整数 $X_i,Y_i,Z_i$（$1\le X_i,Y_i,Z_i\le 10^6$）。

输出格式

一行一个正整数表示答案。

2
2 5 3
1 4 4

12

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

38500

提示

样例解释

• 样例 $1$ 解释：买 $1\times 3\times 4$ 的行李箱。
• 样例 $2$ 解释：买 $55\times 35\times 20$ 的行李箱。

大样例

可以在附件中获得大样例。

样例 $\texttt{0a}$ 是题面中展示的样例。此外：

• $\texttt{0b}$：$n=10^4$，$A_i=33i$，$B_i=C_i=1$。答案为 $33$。
• $\texttt{0c}$：$n=10^5$，$A_i=i,B_i=n+1-i,C_i=10^6$。答案为 $50\,001\,000\,000$。

子任务

本题采用捆绑测试。 | 子任务编号 | 限制 | 得分 | | :---------: | :--------------------- | :-----: | | $1$ | $n,A_i,B_i,C_i\le 10$ | $12$ | | $2$ | $B_i=C_i=1$ | $9$ | | $3$ | $C_i=1$ | $33$ | | $4$ | 无额外限制 | $46$ |