← 返回题目列表

AtCoder · arc029_1

A. 高桥君和肉

中文机器翻译题面 查看原题

問題文

高桥要和他的朋友们去露营。

高桥君和他的朋友也有同样的表现。 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