99991344 - 做饭

高桥君要制作 N 道不同的菜肴,每道菜肴制作需要连续使用烤箱 T_i 分钟。不能同时为两道以上的菜肴使用同一个烤箱。

当有两个烤箱可供使用时,最快需要多少分钟才能制作完所有 N 道菜肴?不考虑除使用烤箱外的其他时间。

输入

输入将以以下格式从标准输入中给出:

N
T_1 T_2 ... T_N

制約

  • 1\ \leq\ N\ \leq\ 100
  • 1\ \leq\ T_i\ \leq\ 10^3
  • 输入的所有值均为整数

输出

请输出答案。

样例

输入

5
8 3 7 2 5

输出

13

输入

2
1000 1

输出

1000

输入

9
3 14 15 9 26 5 35 89 79

输出

138

提示

Sample Explanation 1

例如,当两个烤箱的使用方式如下时,可以在 13 分钟内制作完所有菜肴:

  • 第一个烤箱:按顺序制作菜肴时间 8 + 5 = 13
  • 第二个烤箱:按顺序制作菜肴时间 3 + 7 + 2 = 12
时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题