问题描述

高桥君和他的朋友决定一起去露营。

高桥君和他的朋友有两台性能相同的烧烤炉，每个烧烤炉可以同时烤肉。一旦将肉放在烧烤炉上，就不能取出肉或者换另一块肉。当肉烤熟后可以取出来。不能将一块肉横跨两台烧烤炉。此外，共有 N 块肉，每块肉都被编号从 1 到 N。无论是哪一台烧烤炉，烤一块肉的时间为 t_i。将肉放入烧烤炉和取出肉的操作不需要时间。

高桥君负责烤肉，需要烤完所有的 N 块肉。大家都很饿，所以想要尽量减少烤肉的时间。

求烤完所有肉需要的最少时间。

输入

输入数据以以下格式从标准输入中给出。

$N$ $t_1$ $t_2$ : $t_N$

• 第一行是一个整数 $N$（$1 \leq N \leq 4$），表示肉的数量。
• 第二行到第 N+1 行是关于每块肉的信息。第 i+1 行上是整数 $t_i$（$1 \leq t_i \leq 50$），表示烤肉 i 所需时间。

输出

输出一个整数，表示烤完所有肉需要的最少时间。最后要换行。

输入示例1

4
4
6
7
10

输出示例1

14

其中一台烧烤炉烤肉 1 和肉 4，另一台烧烤炉烤肉 2 和肉 3（下图为参考图）。

输入示例2

3
1
2
4

输出示例2

4

一台烧烤炉烤肉 3 的同时，另一台烧烤炉烤剩下的所有肉。

输入示例3

1
29

输出示例3

29