现在,G○○gle Code Jam 的地区赛即将开始。 据说坐在前排的男生的 ID 是 omeometo。 据说坐在后排的男生的 ID 是 jellies。 回忆东京大学时代,记得有类似 ID 的同伴,但我的同伴应该一个个都是美少女。
他们手上拿着一本桌子上画着蚂蚁插图的书。 那难道是……最先全面涵盖编程竞赛算法、现在已经被禁止发行的传说之书《编程竞赛挑战书》吗? 我趁 omeometo 去厕所的时候,借来看了一下,打算读读。
编程竞赛挑战书
…然而,我一瞬间就把书读完了。 真是没劲。太简单了。 就算是本稍微有些年份的书,也不知怎么想的竟然会把这种内容拿去卖。
比如说,最初的三角形问题。这个,太简单到根本不值一提。如果是我的话,会这样做。
問題
N 书上有一条直直的棒。棒 i 的长度是 ai 。 你要从那些棍子中选出 6 根, 用它们各自的 3 根,尝试制作 2 个三角形。 3 根棍子分别作为三角形的边,两个棍子接触的位置仅限于棍子的端点。 也就是说,不允许使用棍子的一部分作为三角形的边,必须使用整根棍子作为边。 此外,不考虑棍子的粗细,三角形必须具有正面积。
求 2 个三角形周长之和的最大值。 如果无法制作 2 个三角形,则答案为 0。
入力
输入的第一行包含一个整数 N 。 接下来的 N 线 i 行中,每行包含一个整数 ai 被写下。
出力
输出答案整数。
制約
- 1 ≤ N ≤ 105
- 1 ≤ ai ≤ 1015
部分点
针对该问题的判断设置了一组20分的测试用例。 该组中包含的测试用例的输入满足以下条件。
- 1 ≤ N ≤ 100
入出力例
入力例:
6 1 1 1 1 1 1
输入例对应的输出:
6