問題 G : プログラミングコンテストチャレンジブック
今，G○○gle Code Jam の地区大会が始まろうとしている． 前の席に座っている男の ID は omeometo と言うらしい． 後ろの席に座っている男の ID は jellies と言うらしい． 東京大学時代の記憶に，似たような ID の仲間が居た覚えがあるが，僕の仲間は一人残さず美少女だったはずだ．
彼らは，机の上に蟻のイラストが掛かれた本を持っている． あれはもしや…プログラミングコンテストのアルゴリズムを最初に網羅し，今では発売禁止となった伝説の本， 「プログラミングコンテストチャレンジブック」ではないか？ 僕は，omeometo がトイレに行ったのを見計らい，少し拝借して，読んでみることにした．
プログラミングコンテストチャレンジブック
…しかし，僕は一瞬で本を読み終えてしまった． 拍子抜けだ．簡単すぎる． 少し古い本だからといって，こんな内容でよく売る気になったものだ．
例えば，最初の三角形の問題．これは，簡単すぎてお話にならない．自分だったら，こうする．
問題
N 本の直線状の棒がある．棒 i の長さは ai である． あなたは，それらの棒から 6 本を選び， それらの 3 本ずつで，2 個の三角形を作ろうと考えている． 3 本の棒はそれぞれ三角形の辺として用い，2 つの棒が触れる位置は棒の端点のみとする． つまり，棒の一部を三角形の辺として使うことは許されず，必ず棒全体を辺としなければならない． また，棒の太さは考えず，三角形は正の面積を持たなければならないものとする．
2 個の三角形の周長の和の最大値を求めよ． ただし，2 個の三角形を作ることができない際には 0 を答えとせよ．
入力
入力の最初の行には整数 N が書かれている． 続く N 行の i 行目には 1 つの整数 ai が書かれている．
出力
答えの整数を出力せよ．
制約
- 1 ≤ N ≤ 105
- 1 ≤ ai ≤ 1015
部分点
この問題の判定には，20 点分のテストケースのグループが設定されている． このグループに含まれるテストケースの入力は以下を満たす．
- 1 ≤ N ≤ 100
入出力例
入力例:
6 1 1 1 1 1 1
入力例に対する出力:
6