問題文
高桥要和他的朋友们去露营。
高桥君和他的朋友也有同样的表现。 2 它有两个烤肉机,您可以将肉放在每个烤肉机上并平行烧烤。一旦将肉放在烤炉上,在肉煮熟之前,您不能将其从烤炉上取出或将其他肉放在烤炉上。肉煮熟后就可以取出来了。2 穿过两个烤肉架 1 不能放置两块肉。还有,全是肉 N 可用于肉类。 编号至 1 我决定将所有值添加到 N 。肉 使用任一烤肉机烧烤 i 都需要时间。 需要 t_i 。把肉放在烤肉机上再拿出来并不需要太多时间。
高桥负责烤肉。N 我决定烤所有的肉。由于每个人都饿了,我们希望尽量减少烤所有肉所需的时间。
求烤所有肉所需的最短时间。
入力
输入将以以下形式从标准输入给出。
N t_1 t_2 : t_N
- 1 行是一个整数,表示肉块的数量。 给出 N (1 ≦ N ≦ 4) 。这是肉 N 表示有。
- 2 在 N 行提供有关肉的信息。N 行数过多 i 行是一个整数 写着 t_i ,就是肉的意思。 烘烤需要多长时间 i 烘烤所需的时间 t_i (1 ≦ t_i ≦ 50) 。
出力
烧烤所有肉类所需的最短时间。 在 1 行输出。还在输出末尾添加换行符。
入力例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