問題 G : プログラミングコンテストチャレンジブック

今，G○○gle Code Jam の地区大会が始まろうとしている．前の席に座っている男の ID は omeometo と言うらしい．後ろの席に座っている男の ID は jellies と言うらしい．東京大学時代の記憶に，似たような ID の仲間が居た覚えがあるが，僕の仲間は一人残さず美少女だったはずだ．

彼らは，机の上に蟻のイラストが掛かれた本を持っている．あれはもしや…プログラミングコンテストのアルゴリズムを最初に網羅し，今では発売禁止となった伝説の本，「プログラミングコンテストチャレンジブック」ではないか？僕は，omeometo がトイレに行ったのを見計らい，少し拝借して，読んでみることにした．

プログラミングコンテストチャレンジブック

…しかし，僕は一瞬で本を読み終えてしまった．拍子抜けだ．簡単すぎる．少し古い本だからといって，こんな内容でよく売る気になったものだ．

例えば，最初の三角形の問題．これは，簡単すぎてお話にならない．自分だったら，こうする．

問題

N 本の直線状の棒がある．棒 i の長さは a_i である．あなたは，それらの棒から 6 本を選び，それらの 3 本ずつで，2 個の三角形を作ろうと考えている． 3 本の棒はそれぞれ三角形の辺として用い，2 つの棒が触れる位置は棒の端点のみとする．つまり，棒の一部を三角形の辺として使うことは許されず，必ず棒全体を辺としなければならない．また，棒の太さは考えず，三角形は正の面積を持たなければならないものとする．

2 個の三角形の周長の和の最大値を求めよ．ただし，2 個の三角形を作ることができない際には 0 を答えとせよ．

入力

入力の最初の行には整数 N が書かれている．続く N 行の i 行目には 1 つの整数 a_i が書かれている．

出力

答えの整数を出力せよ．

制約

1 ≤ N ≤ 10⁵
1 ≤ a_i ≤ 10¹⁵

部分点

この問題の判定には，20 点分のテストケースのグループが設定されている．このグループに含まれるテストケースの入力は以下を満たす．

1 ≤ N ≤ 100

入出力例

入力例:

入力例に対する出力: