No.1045 直方体大学

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 83
作問者 : SuunnSuunn / テスター : xenon_motsuxenon_motsu
3 ProblemId : 3622 / 出題時の順位表
問題文最終更新日: 2020-05-01 21:30:35

問題文

 高橋くんは直方体大学(略称:直大)の学生です。

 直方体大学は卒業制作の季節です。この大学には、卒業制作で少しでも手を抜いた者は留年させられるという噂があるので、高橋くんは少しでも良いものを作りたいです。

 高橋くんは、あらかじめ卒業制作に向けて集めておいた$N$個の直方体を積み重ねてモニュメントを作ることにしました。$i$番目の直方体の$3$辺の長さはそれぞれ$A_i,B_i,C_i$でした。高橋くんがモニュメントを作る条件として、$1$つの直方体の上の面に直接接して積み重ねられる直方体はただ$1$つであること、下の直方体より縦または横の大きさが大きい直方体を上に積んではいけないこと、上の直方体は下の直方体の縦横どちらかの辺に対して平行な辺が存在するように置かねばならないことがあります。逆に、上の条件を満たす限りはどのような積み方をしてもよく、$3$辺をそれぞれ縦、横、高さのどれに合わせるような向きに使っても構いません。

 モニュメントの良さは、その高さと等しいです。高橋くんが作ることのできる、最も良いモニュメントの良さを求めてください。

(21:29追記 すべての直方体を使い切る必要はありません。使う直方体が1つでも構いません。)

入力

$N$
$A_1\ B_1\ C_1$
$A_2\ B_2\ C_2$
$\vdots$
$A_N\ B_N\ C_N$

$1 \le N \le 16$
$1 \le A_i,B_i,C_i \le 10^7$
入力は全て整数である

出力

高橋くんが作ることのできるモニュメントの良さの最大値を出力してください。

サンプル

サンプル1
入力
1
1 2 3
出力
3

長さ$3$の辺を高さにする向きに置くと良いです。

サンプル2
入力
2
2 7 3
5 1 4
出力
8

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。