You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

马上开学了, 你才发现没有衣服穿了

题目描述

你要洗 $n$ 件衣服， 每件衣服要用 $a_i$ 的时间。

好处是你家有 $2$ 个洗衣机, 你想快点洗完衣服出去玩, 现在你想知道, 最快多久可以洗完所有衣服.

输入格式

第一行一个整数 $n$, 表示有多少件待洗的衣服

第二行 $n$ 个整数 $a_i$ 表示洗第 $i$ 件衣服所需要的时间.

输出格式

输出一个整数表示最快多久可以洗完所有的衣服

样例 #1

样例输入 #1

5
7 2 5 8 3

样例输出 #1

13

样例1解释

第一个洗衣机洗 $7, 2, 3$, 第二个洗衣机洗 $5, 8$ , 可以在13时刻洗完所有衣服

样例 #2

样例输入 #2

9
3 5 35 89 79 14 15 9 26

样例输出 #3

138

提示

• $1\ \leq\ n\ \leq\ 100$
• $1\ \leq\ a_i\ \leq\ 10^3$