時間制限 : sec, メモリ制限 : KB
Japanese

問題 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