B - 引越しできるかな？ Editorial /

Time Limit: 2 sec / Memory Limit: 64 MB

問題文

この春から新生活を始める今城くんは引越しを考えています。
そのため、自分の荷物をダンボールに梱包しなければなりません。
そこで、引越し業者「AtCoder株式会社」にダンボールを注文することにしました。

幸運なことに、AtCoder株式会社では「新生活応援キャンペーン」を行なっており、あるサイズのダンボールなら 1 種類だけ無料で提供しています。
これに目をつけた今城くんは、自分の荷物を全て梱包できるようなサイズのダンボールを大量に注文することで、お金を節約することにしました。
今城くんが注文しなければならないダンボールの容積の最小値はいくらでしょうか

また、今城くんは 1 つのダンボールに自分の荷物を 1 つだけ梱包します。
さらに、今城くんは荷物が運送中に壊れることを防ぐため、斜めに入れることはありません。
つまり、荷物の少なくとも1つの面が、ダンボールか他の荷物のある面にぴったりとくっつくように梱包します。

入力

入力は以下の形式で標準入力から与えられる。 
C
N_{0} M_{0} L_{0}
N_{1} M_{1} L_{1}
:
N_{C-1} M_{C-1} L_{C-1}
  1. 入力 C+1 行ある。
  2. 1 行目には今城くんの荷物の数を表す整数 C(1≦C≦100) が与えられる。
  3. 2 行目から C+1 行目までの C 行では、今城くんの荷物のタテとヨコと高さがそれぞれ半角スペース区切りで与えられる。
    • N_{i} は今城くんが持っている荷物のタテの長さです。
    • M_{i} は今城くんが持っている荷物のヨコの長さです。
    • L_{i} は今城くんが持っている荷物の高さです。
    • 1≦N_{i},M_{i},L_{i}≦100 かつ、それぞれの値は整数であることが保証されています。

部分点

  • 1≦C≦10 を満たす入力にのみ正解した場合、部分点として 40 点が与えられる。

出力

今城くんが注文しなければならないダンボールの容積の最小値を 1 行で出力すること。
また、出力の最後には改行をいれること。

入力例 1

2
10 20 30
20 20 20

出力例 1

12000
  • 20*20*30のダンボールを用意すれば、すべての荷物を梱包することが可能です。

入力例 2

3
10 20 30
20 20 20
30 20 10

出力例 2

12000
  • 向きを変えて入れることにより、20*20*30のダンボールで梱包することが可能です。

入力例 3

4
10 20 30
20 20 20
30 20 10
10 40 10

出力例 3

16000
  • これも向きを変えることにより、40*20*20のダンボールで梱包することが可能です。

入力例 4

2
10 10 10
11 1 1

出力例 4

1100
  • 荷物を傾けて入れることは出来ないので、11*10*10のダンボールが必要になります。