Yet Another MAD TEAM

問題文

$N$ 人のメンバー候補がおり、それぞれの人は、パワー・スピード・テクニック・知識・発想力の $5$ 種類の能力値を持っています。
$i$ 番目の人のパワーは $A_i$ 、スピードは $B_i$ 、テクニックは $C_i$ 、知識は $D_i$ 、発想力は $E_i$ です。
あなたは、$N$ 人のメンバー候補から $3$ 人を選び、$1$ つのチームを作ります。
チーム全体のパワーをチームメンバーのパワーの最大値で定義します。スピード・テクニック・知識・発想力についても同様に定義します。
チームの総合力を、チーム全体の $5$ 種類の能力値の合計で定義します。
チームの総合力としてありえる最大値を求めてください。

制約

• 入力は全て整数
• $3 ≤ N ≤ 3000$
• $1 ≤ A_i, B_i, C_i, D_i, E_i ≤ 1000$

入力

入力は以下の形式で標準入力から与えられる。

$N$
$A_1$ $B_1$ $C_1$ $D_1$ $E_1$
$A_2$ $B_2$ $C_2$ $D_2$ $E_2$
$\vdots$
$A_N$ $B_N$ $C_N$ $D_N$ $E_N$

出力

答えを出力せよ。

サンプル

3
3 9 6 4 6
6 9 3 1 1
8 8 9 3 7

37

$3$ 人全員をチームに入れるほかありません。
この時、チーム全体の各能力値は以下のようになります。

• チーム全体のパワー : $\max(3, 6, 8) = 8$
• チーム全体のスピード : $\max(9, 9, 8) = 9$
• チーム全体のテクニック : $\max(6, 3, 9) = 9$
• チーム全体の知識 : $\max(4, 1, 3) = 4$
• チーム全体の発想力 : $\max(6, 1, 7) = 7$

したがって、チームの総合力は $8 + 9 + 9 + 4 + 7 = 37$ となります。